8612: GRL_5_D : Range Query on a Tree
[Creator : ]
Description
Write a program which manipulates a weighted rooted tree $T$ with the following operations:
-
add(v,w): add w to the edge which connects node v and its parent
-
getSum(u): report the sum of weights of all edges from the root to node u
Input
The first line of the input includes an integer $n$, the number of nodes in the tree.
In the next $n$ lines,the information of node $i$ is given in the following format:
$k_i\ c_1\ c_2\ ...\ c_k$ $k_i$ is the number of children of node $i$, and $c_1\ c_2\ ...\ c_{k_i}$ are node IDs of $1$st, $...$ $k$th child of node $i$.
In the next line, the number of queries $q$ is given.
In the next $q$ lines, $i$th query is given in the following format:
or
The first integer represents the type of queries.'0' denotes add(v,w) and '1' denotes getSum(u).
In the next $n$ lines,the information of node $i$ is given in the following format:
$k_i\ c_1\ c_2\ ...\ c_k$ $k_i$ is the number of children of node $i$, and $c_1\ c_2\ ...\ c_{k_i}$ are node IDs of $1$st, $...$ $k$th child of node $i$.
In the next line, the number of queries $q$ is given.
In the next $q$ lines, $i$th query is given in the following format:
0 u v
or
1 u
The first integer represents the type of queries.'0' denotes add(v,w) and '1' denotes getSum(u).
Output
For each getSum query, print the sum in a line.
Constraints
All the inputs are given in integers
$2≤n≤100,000$
$c_j<c_{j+1}\ (1≤j≤k−1)$
$2≤q≤200,000$
$1≤u,v≤n−1$
$1≤w≤10,000$
$2≤n≤100,000$
$c_j<c_{j+1}\ (1≤j≤k−1)$
$2≤q≤200,000$
$1≤u,v≤n−1$
$1≤w≤10,000$
Sample 1 Input
6
2 1 2
2 3 5
0
0
0
1 4
7
1 1
0 3 10
1 2
0 4 20
1 3
0 5 40
1 4
Sample 1 Output
0
0
10
60
Sample 2 Input
4
1 1
1 2
1 3
0
6
0 3 1000
0 2 1000
0 1 1000
1 1
1 2
1 3
Sample 2 Output
1000
2000
3000
Sample 3 Input
2
1 1
0
4
0 1 1
1 1
0 1 1
1 1
Sample 3 Output
1
2
HINT
相同题目：GRL_5_D。