No.2676 A Tourist
Problem Statement
There is a group of $N$ cities numbered from $1$ to $N$, and $N-1$ roads numbered from $1$ to $N-1$. Road $i$ connects city $u_i$ and city $v_i$, and cities connected by a road can be traveled between in both directions. Also, every city is reachable from city $1$ via some number of roads.
You are a staff member of the traffic management bureau of this group of cities. The bureau is responsible for calculating the harshness of travel between cities from data on the bad weather level, which represents how bad the weather is in each city. The bad weather level of city $v$ is denoted by $a_v$, and the harshness of travel between cities $u$-$v$ is defined as follows.
- Let $P$ be the set of cities on the shortest path from city $u$ to $v$ (including $u, v$). The harshness is the sum of the bad weather levels of "the cities that belong to $P$, or that are directly connected to any of them by $1$ road".
Now, you are given as input the bad weather levels $a_1 , a_2 , \dots , a_N$ of the cities at the current time, and information on $Q$ events that will occur in order. There are two types of events, as follows.
0 v x: The bad weather level $a_v$ of city $v$ increased by $x$.1 u v: A citizen made a request to travel from city $u$ to city $v$.
Each time a citizen requests travel between cities, the traffic management bureau is obliged to tell the requesting citizen the harshness of traveling between those cities.
As a staff member of the bureau, for each event of the form 1 u v, output "the harshness of travel between cities $u$-$v$ at that point in time" in chronological order.
Input
The input is given from standard input in the following format.
Here, $\mathrm{event}_i$ represents the format of the $i$-th event that occurred.
$N \space Q$
$a_1$ $a_2$ $\dots$ $a_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$\mathrm{event}_1$
$\mathrm{event}_2$
$\vdots$
$\mathrm{event}_Q$
Output
For each event of the form 1 u v, output "the harshness of travel between cities $u$-$v$ at that point in time" on one line each, in chronological order.
Print a newline at the end.
Constraints
- All inputs are integers.
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq Q \leq 2 \times 10^5$
- $|a_v| \leq 10^9$ ($ 1 \leq v \leq N $)
- $1 \leq u_i , v_i \leq N$ ($1 \leq i \leq N - 1 $)
- $u_i \neq v_i$ ($1 \leq i \leq N - 1 $)
- $\mathrm{event}_i$ is given in the form
0 v xor1 u v($1 \leq i \leq Q$). - For events of the form
0 v x, $1 \leq v \leq N$ and $|x| \leq 10^9$ hold. - For events of the form
1 u v, $1 \leq u , v \leq N$ and $u \neq v$ hold. - An event of the form
1 u vis given at least $1$ time. - It is possible to travel between any $2$ cities using only the given roads.
Sample
Sample 1
Input
7 6 2 -1 4 8 0 5 -3 1 2 1 3 3 4 3 5 6 5 7 5 1 6 7 1 1 5 0 1 -2 0 3 -4 1 1 5 1 4 5
Output
6 15 9 10
The harshness of traveling $6 \rightarrow 7$ is the sum of the bad weather levels of vertices $3,5,6,7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Xelmeph
null
ngtkana
eoeo