[ACM-ICPC 2018 沈阳网络赛] Ka Chang （dfs序+树状数组+分块）
2020-12-13 06:27
Given a rooted tree ( the root is node 11 ) of NN nodes. Initially, each node has zero point.
Then, you need to handle QQ operations. There‘re two types:
1\ L\ X1 L X: Increase points by XX of all nodes whose depth equals LL ( the depth of the root is zero ). (x \leq 10^8)(x≤108)
2\ X2 X: Output sum of all points in the subtree whose root is XX.
Input
Just one case.
The first lines contain two integer, N,QN,Q. (N \leq 10^5, Q \leq 10^5)(N≤105,Q≤105).
The next n-1n−1 lines: Each line has two integer aa,bb, means that node aa is the father of node bb. It‘s guaranteed that the input data forms a rooted tree and node 11 is the root of it.
The next QQ lines are queries.
Output
For each query 22, you should output a number means answer.
文章标题：[ACM-ICPC 2018 沈阳网络赛] Ka Chang （dfs序+树状数组+分块）
文章链接：http://soscw.com/essay/33062.html