PROBLEM LINK
DIFFICULTY
EASY-MEDIUM
PROBLEM
There are N employees under CEO, need not be immediately under him. Every employee has an index between 1 and N. no two employees has same index. Index of CEO is always 0.
Now given an employee, that employee and all the employees under him are considered as a TEAM. Therefore if there are N employees in the company there are N+1 TEAMS (including CEO). Therefore index of a TEAM is the index of the employee leading that TEAM.
Now you have to update and answer the queries accordingly.
EXPLANATION
First you need to do dfs on node with index 0,To get the order of visiting the nodes. Here the advantage of dfs is first it visits all the nodes under it and then it goes to its sibling nodes. This order is kept in an array seg[] and we should maintain other two arrays start[] and end[] to keep track of the nodes starting index and ending index.
Code:
void dfs(ll cur) {
start[cur] = cnt;
seg[cnt] = sal[cur];
cnt++;
rep(arr[cur].size()) dfs(arr[cur][i]);
end[cur] = cnt-1;
}
Now we should construct the segment tree for seg[], now it becomes the classical problem of getting the maximum salary and updating the salary in the given range.
