問題一覧 > 通常問題

No.2676 A Tourist

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 32
作問者 : NokonoKotlin / テスター : Xelmeph nu50218 null ngtkana eoeo
お気に入りにしたユーザー ProblemId : 10671 / 自分の提出
問題文最終更新日: 2024-03-15 21:22:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 421 (NUPC2023) (順位表) の他の問題:

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 x or 1 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 v is 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もしくは右上の雲マークをクリックしてアカウントを作成してください。