11270: [yosupo] Tree - Vertex Get Range Contour Add on Tree
[Creator : ]
Description
Given a tree with $N$ vertices, where the $i$-th edge connects vertices $u_i$ and $v_i$. Initially a value $a_i$ is written on the vertex $i$. Process the following $Q$ queries in order:
- `0 $p$ $l$ $r$ $x$`: $a_i \leftarrow a_i+x$ for all the vertices $i$ whose distance from the vertex $p$ is in $[l,r)$.
- `1 $p$`: Print $a_p$.
- `0 $p$ $l$ $r$ $x$`: $a_i \leftarrow a_i+x$ for all the vertices $i$ whose distance from the vertex $p$ is in $[l,r)$.
- `1 $p$`: Print $a_p$.
Input
$N$ $Q$
$a_0$ $\cdots$ $a_{N-1}$
$u_0$ $v_0$
$\vdots$
$u_{N-2}$ $v_{N-2}$
$\mathrm{Query}_0$
$\vdots$
$\mathrm{Query}_{Q-1}$
$a_0$ $\cdots$ $a_{N-1}$
$u_0$ $v_0$
$\vdots$
$u_{N-2}$ $v_{N-2}$
$\mathrm{Query}_0$
$\vdots$
$\mathrm{Query}_{Q-1}$
Constraints
- $1 \leq N \leq 10^5$
- $1 \leq Q \leq 2\times 10^5$
- $-1\times 10^9 \leq a_i \leq 10^9$
- $0 \leq u_i, v_i \leq N-1$
- $0 \leq p \leq N-1$
- $0 \leq l \lt r \leq N$
- $-1\times 10^9 \leq x \leq 10^9$
- $1 \leq Q \leq 2\times 10^5$
- $-1\times 10^9 \leq a_i \leq 10^9$
- $0 \leq u_i, v_i \leq N-1$
- $0 \leq p \leq N-1$
- $0 \leq l \lt r \leq N$
- $-1\times 10^9 \leq x \leq 10^9$
Sample 1 Input
9 16
1 10 100 1000 10000 100000 1000000 10000000 100000000
0 1
1 2
1 3
3 4
3 5
0 6
6 7
6 8
0 0 1 3 1
1 0
1 1
1 7
1 4
0 3 0 9 10
1 2
1 3
0 6 1 2 100
1 6
1 7
1 0
1 1
0 2 5 9 100
1 5
1 8
Sample 1 Output
1
11
10000001
10000
111
1011
1000011
10000111
111
21
100010
100000111
Sample 2 Input
1 3
1
1 0
0 0 0 1 10
1 0
Sample 2 Output
1
11