3751 . [模板題] Dynamic Tree Vertex Add Path Sum
TopCoder
Tags
Description
Given tree of $N$ vertices. Edges are $(u_ i, v_ i)$. Value $a_ i$ is written on vertex $i$.
Process the following $Q$ queries in order. You can assume that the graph is always the tree while processing the queries.
0 u v w x: Delete a edge $(u, v)$, and add $(w, x)$.1 p x: $a_ p \gets a_ p + x$2 u v: Print the sum of values of vertices of the path between $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 7 1 10 100 1000 10000 0 1 1 2 2 3 1 4 2 0 3 1 1 100000 2 3 4 0 1 2 2 0 2 3 4 0 2 3 3 1 2 2 3
Sample Output 1
1111 111110 111111 101111
Hints
- $1 \leq N, Q \leq 200,000$
- $0 \leq a_ i, x \leq 10^ 9$
- $0 \leq p, u_ i, v_ i < N$
- $(u_ i, v_ i)$ is tree.
- for type 0 queries, there is a edge $(u, v)$.
- The graph is always tree.
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|