Departments and Budgets
A rooted tree (root 1) has a value per node. Support U v x (assign node v's value to x) and Q v (print the SUM over v's whole subtree).
Input: the first line has N and Q; the second line has the N initial values; the next N−1 lines have edges; the next Q lines are operations.
Output: one line per Q operation.
Constraints:
- 1 ≤ N, Q ≤ 105
- |values| ≤ 104
Sample Tests
Input 1
3 3 1 2 3 1 2 1 3 Q 1 U 2 10 Q 1
Output 1
6 14
Input 2
1 1 5 Q 1
Output 2
5
Discussion (opens after you solve — no spoilers before)
No comments yet.