TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

Given a tree of $N$ vertices. Edges are $(u_ i, v_ i)$. Value $a_ i$ is written on the vertex $i$.

Process the following $Q$ queries in order:

  • 0 p x: $a_ p \gets a_ p + x$
  • 1 u v: Print the sum of the values of vertices of the path between vertex $u$ and $v$ (inclusive).

Input Format

$N$ $Q$
$a_ 0$ $a_ 1$ ... $a_ {N - 1}$
$u_ 0$ $v_ 0$
$u_ 1$ $v_ 1$
:
$u_ {N - 2}$ $v_ {N - 2}$
$\textrm{Query}_ 0$
$\textrm{Query}_ 1$
:
$\textrm{Query}_ {Q - 1}$

Output Format

Sample Input 1

5 5
1 10 100 1000 10000
0 1
1 2
2 3
1 4
1 0 3
1 2 4
0 1 100000
1 1 3
1 3 2

Sample Output 1

1111
10110
101110
1100

Hints

  • $1 \leq N, Q \leq 5 \times 10^ {5}$
  • $0 \leq a_ i, x \leq 10^ {9}$
  • $0 \leq p, u_ i, v_ i < N$

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
12 5000 2097152 2097152
13 5000 2097152 2097152
14 5000 2097152 2097152
15 5000 2097152 2097152
16 5000 2097152 2097152
17 5000 2097152 2097152
18 5000 2097152 2097152