AT_ddcc_2016_final_e 根付き木とクエリ

[problemUrl]: https://atcoder.jp/contests/ddcc2016-final/tasks/ddcc_2016_final_e $ 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 $ で確認してください。

入力は以下の形式で標準入力から与えられる。 > $ 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\ ≦\ 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 $ はいずれも整数 ### Sample Explanation 1 はじめに下図のようなグラフが与えられます。 !\[14719568c70b794384d9267713fc28f1.png\](https://atcoder.jp/img/ddcc2016-qual/14719568c70b794384d9267713fc28f1.png) `1 1 2 5`というクエリを処理したあとの辺の長さは下図のように変化します。$ 2 $ 代目の頂点である頂点 $ 2,\ \,\ 4 $ と $ 3 $ 代目の頂点である頂点 $ 3,\ 5,\ 6 $ をつなぐ辺の長さに $ 5 $ が加算されます。 !\[344f145215af530aec7fe65e98c2ec9c.png\](https://atcoder.jp/img/ddcc2016-qual/344f145215af530aec7fe65e98c2ec9c.png) さらに、`1 4 1 2`というクエリを処理したあとの辺の長さは下図のように変化します。$ 1 $ 代目の頂点である頂点 $ 4 $ と $ 2 $ 代目の頂点である頂点 $ 3,\ \,\ 6 $ をつなぐ辺の長さに $ 2 $ が加算されます。 !\[293c37ff6545b9d841490366cc4f1153.png\](https://atcoder.jp/img/ddcc2016-qual/293c37ff6545b9d841490366cc4f1153.png) ### Sample Explanation 2 加算の対象となる辺が存在するとは限りません。