# Dynamic Tree Subtree Add Subtree Sum

AC一覧

## Problem Statement問題文

You are given a tree with $N$ vertices. $i$-th edge connects vertex $u_i$ and vertex $v_i$. A number $a_i$ is written on vertex $i$.

Process $Q$ queries of the following types in order :

• 0 $u$ $v$ $w$ $x$: remove edge $(u, v)$ and add a new edge $(w, x)$. It is guranteed that the graph remains a tree after processing.
• 1 $v$ $p$ $x$: focusing on edge $(v, p)$ and regarding $p$ as a parent, add $x$ to values of all vertices in the subtree of vertex $v$.
• 2 $v$ $p$: focusing on edge $(v, p)$ and regarding $p$ as a parent, find the sum over values of all vertices in the subtree of vertex $v$.

$N$ 頂点の木が与えられます。$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。また、頂点 $i$ には値 $a_i$ が書かれています。

• 0 $u$ $v$ $w$ $x$ : 辺 $(u, v)$ を削除し、辺 $(w, x)$ を作成する。処理後もグラフが木であることが保証される。
• 1 $v$ $p$ $x$ : 辺 $(v, p)$ について、頂点 $p$ を親としたときの頂点 $v$ の部分木に含まれる頂点の値にそれぞれ $x$ を足す。
• 2 $v$ $p$ : 辺 $(v, p)$ について、頂点 $p$ を親としたときの頂点 $v$ の部分木に含まれる頂点の値の総和を出力する。

## Constraints制約

• $2 \le N \le 200{,}000$
• $1 \le Q \le 200{,}000$
• $0 \le a_i \le 10^{7}$
• $0 \le u_i, v_i < N$
• The graph is a tree
• For queries of type 0 $u$ $v$ $w$ $x$ :
• $0 \le u, v, w, x \lt N$
• Edge $(u, v)$ exists when processing a query of this type
• The grpah remains a tree after processing
• For queries of type 1 $v$ $p$ $x$ :
• $0 \le v, p \lt N$
• $0 \le x \le 10^{7}$
• Edge $(v, p)$ exists when processing a query of this type
• For queries of type 2 $v$ $p$ :
• $0 \le v, p \lt N$
• Edge $(v, p)$ exists when processing a query of this type

• $2 \le N \le 200{,}000$
• $1 \le Q \le 200{,}000$
• $0 \le a_i \le 10^{7}$
• $0 \le u_i, v_i < N$
• 与えられるグラフは木
• 0 $u$ $v$ $w$ $x$形式のクエリについて
• $0 \le u, v, w, x \lt N$
• その時点で辺 $(u, v)$ は存在する
• 処理後もグラフは木
• 1 $v$ $p$ $x$形式のクエリについて
• $0 \le v, p \lt N$
• $0 \le x \le 10^{7}$
• その時点で辺 $(v, p)$ は存在する
• 2 $v$ $p$形式のクエリについて
• $0 \le v, p \lt N$
• その時点で辺 $(v, p)$ は存在する

## Input入力

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$u_0$ $v_0$
$u_1$ $v_1$
$\hspace{11pt} \vdots$
$u_{N - 2}$ $v_{N - 2}$
$\mathrm{Query}_0$
$\mathrm{Query}_1$
$\hspace{14pt} \vdots$
$\mathrm{Query}_{Q - 1}$

### # 1

5 7
1 10 100 1000 10000
0 1
1 2
2 3
1 4
2 1 0
1 1 4 100000
2 2 3
0 1 2 2 0
2 0 2
0 2 3 3 1
2 1 4
11110
310111
210011
401111

Timelimit: 5 secs

Before submitting, please confirm terms and conditions