No.900 aδδitivee

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 45
作問者 : niuezniuez / テスター : Lemma299Lemma299
1 ProblemId : 3406 / 出題時の順位表

問題文

niuez くんは木を成長させる添加物を作り出したので,この力を試してみようと思いました.
しかし,見当もつかない大きさになるのは危険なのであらかじめシミュレーションをすることにしました.

$0$ から $N-1$ までの番号のついた $N$ 頂点,$N-1$ 辺からなる頂点 $0$ を根とする有向木があります.木の $i \ (0 \leq i < N-1)$ 番目の辺は頂点 $u_i$ から $v_i$ へ向かう辺であり,$w_i$ の重みを持ちます.

次の $Q$ 個の ${\rm query}$ を順に処理してください.

  • $1 \ a \ x$
    • ${\rm query}\ 1$:頂点 $a$ の部分木に含まれる辺すべての重みに $x$ を加算する.
  • $2 \ b$
    • ${\rm query}\ 2$:頂点 $0$ から $b$ へのパスに含まれる辺の重みの総和を求める.

入力

$N$
$u_0 \  v_0 \  w_0$
$\cdots$
$u_{N-2} \  v_{N-2} \  w_{N-2}$
$Q$
${\rm query}_0$
$\cdots$
${\rm query}_{Q-1}$
  • $2 \leq N \leq 10^5$
  • $0 \leq u_i, v_i < N$
    • $u_i \neq v_i$
    • $(u_i, v_i) = (u_j, v_j) \Leftrightarrow i = j$
  • $0 \leq w_i \leq 10^5$
  • $1 \leq Q \leq 10^5$
  • ${\rm query}_i$ は以下のいずれかの形式です.
    • $1 \ a \ x $
      • $0 \leq a < N$
      • $0 \leq x \leq 10^5$
    • $2 \ b$
      • $0 \leq b < N$
  • 入力はすべて整数

出力

${\rm query}\ 2$ の答えを順番に改行区切りで出力してください.

サンプル

サンプル1
入力
7
0 1 1
0 2 2
1 3 3
1 4 4
2 5 5
2 6 6
7
2 3
2 5
1 2 100
2 5
2 6
1 0 1000
2 6
出力
4
7
107
108
2108

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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。