English · Original
Chinese · Translation
Formal · Original
You are given a directed weighted graph with _n_ nodes and 2_n_ - 2 edges. The nodes are labeled from 1 to _n_, while the edges are labeled from 1 to 2_n_ - 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_.
You are given _q_ queries. There are two types of queries
* 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_
Given these queries, print the shortest path lengths.
## 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 2_n_ - 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_ ≤ 2_n_ - 2.
* _a__n_, _a__n_ + 1, ..., _a_2_n_ - 2 will be distinct and between 2 and _n_.
The next _q_ lines will contain 3 integers, describing a query in the format described in the statement.
All edge weights will be between 1 and 106.
## Output
For each type 2 query, print the length of the shortest path in its own line.
[samples]
你被给定一个有 #cf_span[n] 个节点和 #cf_span[2n - 2] 条边的有向加权图。节点编号从 #cf_span[1] 到 #cf_span[n]，边编号从 #cf_span[1] 到 #cf_span[2n - 2]。图的边可以分为两部分。
你被给定 #cf_span[q] 个查询。查询有两种类型：
根据这些查询，输出最短路径长度。
输入的第一行包含两个整数 #cf_span[n, q]（#cf_span[2 ≤ n, q ≤ 200 000]），分别表示节点数和查询数。
接下来的 #cf_span[2n - 2] 行每行包含三个整数 #cf_span[ai, bi, ci]，表示一条从节点 #cf_span[ai] 指向节点 #cf_span[bi]、权重为 #cf_span[ci] 的有向边。
其中前 #cf_span[n - 1] 行描述一棵以节点 #cf_span[1] 为根、边指向远离根方向的有根生成树；后 #cf_span[n - 1] 行满足 #cf_span[bi = 1]。
更具体地：
接下来的 #cf_span[q] 行每行包含三个整数，描述题目中所述格式的查询。
所有边权均在 #cf_span[1] 到 #cf_span[106] 之间。
对于每个类型 2 的查询，请在单独一行中输出最短路径的长度。
## Input
输入的第一行包含两个整数 #cf_span[n, q]（#cf_span[2 ≤ n, q ≤ 200 000]），分别表示节点数和查询数。接下来的 #cf_span[2n - 2] 行每行包含三个整数 #cf_span[ai, bi, ci]，表示一条从节点 #cf_span[ai] 指向节点 #cf_span[bi]、权重为 #cf_span[ci] 的有向边。前 #cf_span[n - 1] 行描述一棵以节点 #cf_span[1] 为根、边指向远离根方向的有根生成树；后 #cf_span[n - 1] 行满足 #cf_span[bi = 1]。更具体地：边 #cf_span[(a1, b1), (a2, b2), ... (an - 1, bn - 1)] 构成一棵以节点 #cf_span[1] 为根、边指向远离根方向的有根生成树。对于 #cf_span[n ≤ j ≤ 2n - 2]，有 #cf_span[bj = 1]。且 #cf_span[an, an + 1, ..., a2n - 2] 互不相同，且取值在 #cf_span[2] 到 #cf_span[n] 之间。接下来的 #cf_span[q] 行每行包含三个整数，描述题目中所述格式的查询。所有边权均在 #cf_span[1] 到 #cf_span[106] 之间。
## Output
对于每个类型 2 的查询，请在单独一行中输出最短路径的长度。
[samples]
**Definitions**
Let $ n, q \in \mathbb{Z} $ with $ 2 \leq n, q \leq 200{,}000 $.
Let $ G = (V, E) $ be a directed weighted graph where:
- $ V = \{1, 2, \dots, n\} $ is the set of nodes.
- $ E = E_1 \cup E_2 $, with $ |E_1| = |E_2| = n - 1 $, so $ |E| = 2n - 2 $.
- $ E_1 = \{(a_i, b_i, c_i) \mid i = 1, \dots, n-1\} $: a rooted spanning tree directed away from node 1 (i.e., for each edge, $ a_i $ is parent of $ b_i $, and node 1 is the root).
- $ E_2 = \{(a_i, 1, c_i) \mid i = n, \dots, 2n-2\} $: edges directed **to** node 1 (i.e., $ b_i = 1 $ for all $ i \in \{n, \dots, 2n-2\} $).
Each edge $ e = (u, v, w) \in E $ has weight $ w \in [1, 10^6] $.
Let $ Q = \{(t_j, u_j, v_j) \mid j = 1, \dots, q\} $ be a sequence of queries, where each query has type $ t_j \in \{1, 2\} $:
- Type 1: Update the weight of edge $ e_k $ (identified by input order) to a new value.
- Type 2: Query the shortest path distance from node $ u_j $ to node $ v_j $.
**Constraints**
1. $ 2 \leq n \leq 200{,}000 $, $ 1 \leq q \leq 200{,}000 $.
2. All edge weights are integers in $ [1, 10^6] $.
3. The initial graph structure satisfies:
- $ E_1 $ forms a directed tree rooted at 1 with all edges pointing away from 1.
- $ E_2 $ consists of $ n-1 $ edges each pointing to node 1 (from some node $ \neq 1 $).
4. For type 1 queries, the edge index refers to the input order of the $ 2n-2 $ edges.
5. For type 2 queries, $ u_j, v_j \in V $.
**Objective**
For each query of type 2, compute and output the shortest path distance from node $ u_j $ to node $ v_j $ in $ G $, under dynamically updated edge weights.
API Response (JSON)
{
"problem": {
"name": "B. Diverging Directions",
"description": {
"content": "You are given a directed weighted graph with _n_ nodes and 2_n_ - 2 edges. The nodes are labeled from 1 to _n_, while the edges are labeled from 1 to 2_n_ - 2. The graph's edges can be split into two ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF838B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given a directed weighted graph with _n_ nodes and 2_n_ - 2 edges. The nodes are labeled from 1 to _n_, while the edges are labeled from 1 to 2_n_ - 2. The graph's edges can be split into two ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个有 #cf_span[n] 个节点和 #cf_span[2n - 2] 条边的有向加权图。节点编号从 #cf_span[1] 到 #cf_span[n]，边编号从 #cf_span[1] 到 #cf_span[2n - 2]。图的边可以分为两部分。\n\n你被给定 #cf_span[q] 个查询。查询有两种类型：\n\n根据这些查询，输出最短路径长度。\n\n输入的第一行包含两个整数 #cf_sp...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, q \\in \\mathbb{Z} $ with $ 2 \\leq n, q \\leq 200{,}000 $. \nLet $ G = (V, E) $ be a directed weighted graph where: \n- $ V = \\{1, 2, \\dots, n\\} $ is the set of nodes. \n- $ E ...",
"is_translate": false,
"language": "Formal"
}
]
}