MAXCHILDSUM - Maximum Child Sum
A rooted tree is being built. Initially, there is only one node in the tree, having number 1 and value 0. You are to perform Q (Q<=200000) queries, each of them is one of the following two types:
- 1 X Y - Add a new vertex to the tree with parent X (It's guaranteed that node X is already in the tree) and value Y (1<=Y<=10^9). Its number will be the smallest positive integer that is not a number of a node yet. For example, the first query of this type will add a vertex with number 2, then 3, then 4 and so on.
- 2 X - Consider the children of node X. For each of them, let's sum up the values of all nodes in their subtrees. You are asked to print the maximum of those sums.
Input
The first line contains an integer Q - the number of queries. Each of the next Q lines contains one of the queries.
Output
Print the answers for all queries of the second type, one answer per line.
Example
Input: 7
1 1 3
2 1
2 2
1 2 5
2 1
1 1 4
2 1 Output: 3
0
8
8
hide comments
threat_:
2020-10-31 17:26:33
I have an O(qlogq) offline solution using centroid decomposition.
|
|
DK...:
2018-09-24 22:11:06
bf in one of the queries got ac using scanf/printf metods. i think the time limit must be a bit less. |
|
kaushikd49:
2016-09-06 22:30:33
Can you guys post a few test cases here? |
|
[Rampage] Blue.Mary:
2016-08-26 18:33:05
I've (again) used some evil technique to successfully "attack" this problem :-) |
|
Willy:
2016-08-26 17:00:53
Beautiful problem.
|
|
dips88:
2016-08-24 05:44:16
Can the node have any no of child??
|
|
Rishav Goyal:
2016-08-22 14:36:42
increase the time limit? i dont think it has logn solution per query.
|
Added by: | Extazy |
Date: | 2016-08-22 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |