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$ が書かれています。

以下のクエリ $Q$ 個を処理してください。

  • 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

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions