E - 根付き木とクエリ Editorial /

Time Limit: 5 sec / Memory Limit: 512 MB

配点 : 1500 点

問題文

N 頂点の根付き木が与えられます。 各頂点には 1, \, 2, \, ..., \, N と番号がついており、頂点 1 はこの根付き木の根です。 i(1 ≦ i ≦ N-1) 番目の辺は頂点 A_i と頂点 B_i をつなぐ、長さ C_i の無向辺です。

Q 個のクエリが与えられるので、順番に処理してください。 クエリには 2 種類あり、入力形式とクエリの内容は以下のとおりです。

  • 1 v k x： 頂点 v を根とする部分木において、k 代目の頂点と k+1 代目の頂点をつなぐ辺それぞれについて、辺の長さに x を加算せよ。ここで、頂点 v は 1 代目の頂点と定義され、n 代目の頂点の直接の子であるような頂点は n+1 代目の頂点と定義される。
  • 2 u v： 頂点 u から頂点 v への最短経路長を求めよ。

詳細はサンプル 1 で確認してください。

制約

  • 1 ≦ N, \, Q ≦ 10^{5}
  • 1 ≦ A_i, \, B_i ≦ N
  • 1 ≦ C_i ≦ 10^{5}
  • 1 ≦ u, \, v, \, k ≦ N
  • 1 ≦ x ≦ 10^5
  • 与えられるグラフは木にである
  • 種類 2 のクエリで与えられる頂点 u, \, v は相異なる
  • C_i, \, x はいずれも整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1 C_1
:
A_{N-1} B_{N-1} C_{N-1}
Q
Query_1
:
Query_{Q}

出力

2 u vというフォーマットのクエリに対する答えを、クエリが与えられた順にそれぞれ 1 行ずつ出力せよ。

入力例 1

6
1 2 4
1 4 2
4 3 7
4 5 3
2 6 2
5
1 1 2 5
2 3 5
1 4 1 2
2 6 3
2 2 4

出力例 1

20
27
6

はじめに下図のようなグラフが与えられます。

14719568c70b794384d9267713fc28f1.png

1 1 2 5というクエリを処理したあとの辺の長さは下図のように変化します。2 代目の頂点である頂点 2, \, 4 と 3 代目の頂点である頂点 3, \ 5, \ 6 をつなぐ辺の長さに 5 が加算されます。

344f145215af530aec7fe65e98c2ec9c.png

さらに、1 4 1 2というクエリを処理したあとの辺の長さは下図のように変化します。1 代目の頂点である頂点 4 と 2 代目の頂点である頂点 3, \, 6 をつなぐ辺の長さに 2 が加算されます。

293c37ff6545b9d841490366cc4f1153.png

入力例 2

2
1 2 1
3
1 1 2 10
1 2 2 5
2 1 2

出力例 2

1

加算の対象となる辺が存在するとは限りません。