1525: CF838 - B. Diverging Directions
[Creator : ]
Description
You are given a directed weighted graph with $n$ nodes and $2n-2$ edges. The nodes are labeled from $1$ to $n$, while the edges are labeled from $1$ to $2n-2$. The graph's edges can be split into two parts.
- The first $n-1$ edges will form a rooted spanning tree, with node $1$ as the root. All these edges will point away from the root.
- The last $n-1$ edges will be from node $i$ to node $1$, for all $2≤i≤n$.
- 1 i w: Change the weight of the $i$-th edge to $w$
- 2 u v: Print the length of the shortest path between nodes $u$ to $v$
Input
The first line of input will contain two integers $n,q\ (2≤n,q≤200,000),$ the number of nodes, and the number of queries, respectively.
The next $2n-2$ integers will contain $3$ integers $a_i,b_i,c_i$, denoting a directed edge from node $a_i$ to node $b_i$ with weight $c_i$.
The first $n-1$ of these lines will describe a rooted spanning tree pointing away from node $1$, while the last $n-1$ of these lines will have $b_i=1$.
More specifically,
All edge weights will be between $1$ and $10^6$.
The next $2n-2$ integers will contain $3$ integers $a_i,b_i,c_i$, denoting a directed edge from node $a_i$ to node $b_i$ with weight $c_i$.
The first $n-1$ of these lines will describe a rooted spanning tree pointing away from node $1$, while the last $n-1$ of these lines will have $b_i=1$.
More specifically,
- The edges $(a_1,b_1),(a_2,b_2),... (a_{n-1},b_{n-1})$ will describe a rooted spanning tree pointing away from node $1$.
- $b_j=1$ for $n≤j≤2n-2$.
- $a_n,a_{n+1},...,a_{2n-2}$ will be distinct and between $2$ and $n$.
All edge weights will be between $1$ and $10^6$.
Output
For each type $2$ query, print the length of the shortest path in its own line.
Sample 1 Input
5 9
1 3 1
3 2 2
1 4 3
3 5 4
5 1 5
3 1 6
2 1 7
4 1 8
2 1 1
2 1 3
2 3 5
2 5 2
1 1 100
2 1 3
1 8 30
2 4 2
2 2 4
Sample 1 Output
0
1
4
8
100
132
10