

Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点の木 T が与えられます。 辺 i (1\leq i\leq N-1) は頂点 u _ i と v _ i を結んでおり、重みは w _ i です。
次の 2 種類のクエリが合計 Q 個与えられるので、順に処理してください。
1 i w
:辺 i の重みを w に変更する。2 u v
:頂点 u と頂点 v の距離を出力する。
ただし、木の 2 頂点 u,v の距離とは、u と v を両端点とするパスに含まれる辺の重みの合計として得られる値のうち最小のものです。
制約
- 1\leq N\leq 2\times10^5
- 1\leq u _ i,v _ i\leq N\ (1\leq i\leq N-1)
- 1\leq w _ i\leq 10^9\ (1\leq i\leq N-1)
- 与えられるグラフは木
- 1\leq Q\leq 2\times10^5
- 1 番目の形式のクエリについて、
- 1\leq i\leq N-1
- 1\leq w\leq 10^9
- 2 番目の形式のクエリについて、
- 1\leq u,v\leq N
- 2 番目の形式のクエリが 1 つ以上存在する
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N u _ 1 v _ 1 w _ 1 u _ 2 v _ 2 w _ 2 \vdots u _ {N-1} v _ {N-1} w _ {N-1} Q \operatorname{query} _ 1 \operatorname{query} _ 2 \vdots \operatorname{query} _ Q
ただし、\operatorname{query} _ i は i 個目のクエリを表しており、次の形式のいずれかで与えられる。
1 i w
2 u v
出力
2 番目の形式のクエリの個数を q 個として q 行出力せよ。 j 行目 (1\leq j\leq q) には、2 番目の形式のクエリのうち j 個目のものに対する答えを出力せよ。
入力例 1
5 1 2 3 1 3 6 1 4 9 4 5 10 4 2 2 3 2 1 5 1 3 1 2 1 5
出力例 1
9 19 11
木ははじめ、下の図のようになっています。
各クエリでは、以下のような処理を行います。
- 1 つめのクエリでは、頂点 2 と頂点 3 の距離を出力します。辺 1 と辺 2 をこの順に使うことで重みの合計が 9 であるようなパスが得られ、これが最小なので 9 を出力します。
- 2 つめのクエリでは、頂点 1 と頂点 5 の距離を出力します。辺 3 と辺 4 をこの順に使うことで重みの合計が 19 であるようなパスが得られ、これが最小なので 19 を出力します。
- 3 つめのクエリでは、辺 3 の重みを 1 に変更します。
- 4 つめのクエリでは、頂点 1 と頂点 5 の距離を出力します。辺 3 と辺 4 をこの順に使うことで重みの合計が 11 であるようなパスが得られ、これが最小なので 11 を出力します。
入力例 2
7 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 3 2 1 6 1 1 294967296 2 1 6
出力例 2
5000000000 4294967296
答えが 32\operatorname{bit} 整数に収まらない場合があることに注意してください。
入力例 3
1 1 2 1 1
出力例 3
0
入力例 4
8 1 2 105 1 3 103 2 4 105 2 5 100 5 6 101 3 7 106 3 8 100 18 2 2 8 2 3 6 1 4 108 2 3 4 2 3 5 2 5 5 2 3 1 2 4 3 1 1 107 2 3 1 2 7 6 2 3 8 2 1 5 2 7 6 2 4 7 2 1 7 2 5 3 2 8 6
出力例 4
308 409 313 316 0 103 313 103 525 100 215 525 421 209 318 519
Score : 600 points
Problem Statement
You are given a tree T with N vertices. Edge i (1\leq i\leq N-1) connects vertices u _ i and v _ i, and has a weight of w _ i.
Process Q queries in order. There are two kinds of queries as follows.
1 i w
: Change the weight of edge i to w.2 u v
:Print the distance between vertex u and vertex v.
Here, the distance between two vertices u and v of a tree is the smallest total weight of edges in a path whose endpoints are u and v.
Constraints
- 1\leq N\leq 2\times10^5
- 1\leq u _ i,v _ i\leq N\ (1\leq i\leq N-1)
- 1\leq w _ i\leq 10^9\ (1\leq i\leq N-1)
- The given graph is a tree.
- 1\leq Q\leq 2\times10^5
- For each query of the first kind,
- 1\leq i\leq N-1, and
- 1\leq w\leq 10^9.
- For each query of the second kind,
- 1\leq u,v\leq N.
- There is at least one query of the second kind.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N u _ 1 v _ 1 w _ 1 u _ 2 v _ 2 w _ 2 \vdots u _ {N-1} v _ {N-1} w _ {N-1} Q \operatorname{query} _ 1 \operatorname{query} _ 2 \vdots \operatorname{query} _ Q
Here, \operatorname{query} _ i denotes the i-th query and is in one of the following format:
1 i w
2 u v
Output
Print q lines, where q is the number of queries of the second kind. The j-th line (1\leq j\leq q) should contain the answer to the j-th query of the second kind.
Sample Input 1
5 1 2 3 1 3 6 1 4 9 4 5 10 4 2 2 3 2 1 5 1 3 1 2 1 5
Sample Output 1
9 19 11
The initial tree is shown in the figure below.
Each query should be processed as follows.
- The first query asks you to print the distance between vertex 2 and vertex 3. Edge 1 and edge 2, in this order, form a path between them with a total weight of 9, which is the minimum, so you should print 9.
- The second query asks you to print the distance between vertex 1 and vertex 5. Edge 3 and edge 4, in this order, form a path between them with a total weight of 19, which is the minimum, so you should print 19.
- The third query changes the weight of edge 3 to 1.
- The fourth query asks you to print the distance between vertex 1 and vertex 5. Edge 3 and edge 4, in this order, form a path between them with a total weight of 11, which is the minimum, so you should print 11.
Sample Input 2
7 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 3 2 1 6 1 1 294967296 2 1 6
Sample Output 2
5000000000 4294967296
Note that the answers may not fit into 32-bit integers.
Sample Input 3
1 1 2 1 1
Sample Output 3
0
Sample Input 4
8 1 2 105 1 3 103 2 4 105 2 5 100 5 6 101 3 7 106 3 8 100 18 2 2 8 2 3 6 1 4 108 2 3 4 2 3 5 2 5 5 2 3 1 2 4 3 1 1 107 2 3 1 2 7 6 2 3 8 2 1 5 2 7 6 2 4 7 2 1 7 2 5 3 2 8 6
Sample Output 4
308 409 313 316 0 103 313 103 525 100 215 525 421 209 318 519