問題一覧 > 通常問題

No.1790 Subtree Deletion

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : shiroha_F14shiroha_F14 / テスター : NachiaNachia
0 ProblemId : 7412 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-25 23:51:08

問題文

$N$ 頂点 $N - 1$ 辺から成る、根付き木である無向グラフが与えられます。
各頂点には $1, 2, \ldots, N$ の番号が振られており、グラフの根は頂点 $1$ です。
また、各辺には $1, 2, \ldots, N - 1$ の番号が振られています。$i$ 番目の辺は $L_i$ と $R_i$ を接続しており、非負整数 $A_i$ が書かれています。

$1 \leq i \leq N$ について、$F(i)$ を次のように定義します。

  • 頂点 $i$ の子が存在しない場合、 $F(i)=0$
  • 頂点 $i$ の子が存在する場合、 $F(i) = $ 頂点 $i$ を根とする部分木に含まれる、全ての辺に書かれた非負整数のビットごとの排他的論理和

これから $Q$ 件のクエリが与えられるので、与えられた順に処理してください。
$i$ 件目のクエリは正の整数 $t_i, x_i$ で構成されます。

  • $t_i = 1$ のとき : 頂点 $x_i$ および、頂点 $x_i$ を根とする部分木に含まれるすべての頂点を削除する。ただし、頂点 $x_i$ が削除済みならば何もしない。
  • $t_i = 2$ のとき : $F(x_i)$ を出力する。ただし、頂点 $x_i$ が削除済みならば $0$ を出力する。
ここで、$t_i = 1$ のとき、$2 \leq x_i$ が保証されます。

入力

$N$
$L_1$ $R_1$ $A_1$
$L_2$ $R_2$ $A_2$
$\vdots$
$L_{N-1}$ $R_{N-1}$ $A_{N-1}$
$Q$
$t_1$ $x_1$
$t_2$ $x_2$
$\vdots$
$t_Q$ $x_Q$
  • 入力はすべて整数
  • $2 \leq N \leq 10^5$
  • $1 \leq L_i, R_i \leq N (1 \leq i \leq N - 1)$
  • $0 \leq A_i \leq 10^{18} (1 \leq i \leq N - 1)$
  • 与えられるグラフは木である。
  • $1 \leq Q \leq 10^5$
  • $t_i \in \{1, 2\} (1 \leq i \leq Q)$
  • $t_i = 2$ であるような $i$ が少なくとも $1$ つ以上存在する。
  • $1 \leq i \leq Q, t_i = 1$ を満たす $i$ について
    • $2 \leq x_i \leq N$
  • $1 \leq i \leq Q, t_i = 2$ を満たす $i$ について
    • $1 \leq x_i \leq N$

出力

$t_i = 2$ であるようなクエリの回数が $Q_2$ であるとすると、$Q_2$ 行出力してください。
$j$ 行目には最初から $j$ 回目の $t_i = 2$ であるようなクエリに対する出力を行ってください。

サンプル

サンプル1
入力
4
1 2 5
1 3 4
2 4 6
3
2 1
1 2
2 1
出力
7
4

$1$ つ目のクエリを処理する時点では、頂点 $1$ の部分木に含まれる辺は $\{1, 2, 3\}$ です。
$2$ つ目のクエリで頂点 $\{2, 4\}$、及び辺 $\{1, 3\}$ が削除されます。
最後のクエリを処理する時点で、頂点 $1$ の部分木に含まれる辺は $\{2\}$ です。

サンプル2
入力
5
2 4 8
3 1 3
2 3 5
5 3 9
6
2 3
1 2
2 5
1 2
2 5
2 1
出力
4
0
0
10

サンプル3
入力
7
6 5 17
2 5 4
4 3 11
5 1 13
6 7 13
1 3 5
10
2 1
1 3
2 7
2 6
1 6
1 5
1 6
1 6
2 5
2 7
出力
27
0
13
0
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。