MAXCHILDSUM - Maximum Child Sum

no tags 

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.
Hint: time complexity for type 1 and 2 query are different.

dips88: 2016-08-24 05:44:16

Can the node have any no of child??
RE: No, only between 0 and N-1.

Last edit: 2016-08-24 08:58:40
Rishav Goyal: 2016-08-22 14:36:42

increase the time limit? i dont think it has logn solution per query.
RE: Done :)

Last edit: 2016-08-25 14:33:54

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