Departments and Budgets

Difficulty: 2000 6000 ms 128 MB

fenwick trees euler-tour

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 ≤ 10⁵
• |values| ≤ 10⁴

Sample Tests

3 3
1 2 3
1 2
1 3
Q 1
U 2 10
Q 1

6
14

1 1
5
Q 1

5

Read the Editorial