{"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 parts.\n\n*   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.\n*   The last _n_ - 1 edges will be from node _i_ to node 1, for all 2 ≤ _i_ ≤ _n_.\n\nYou are given _q_ queries. There are two types of queries\n\n*   1 _i_ _w_: Change the weight of the _i_\\-th edge to _w_\n*   2 _u_ _v_: Print the length of the shortest path between nodes _u_ to _v_\n\nGiven these queries, print the shortest path lengths.\n\n## Input\n\nThe 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.\n\nThe 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_.\n\nThe 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.\n\nMore specifically,\n\n*   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.\n*   _b__j_ = 1 for _n_ ≤ _j_ ≤ 2_n_ - 2.\n*   _a__n_, _a__n_ + 1, ..., _a_2_n_ - 2 will be distinct and between 2 and _n_.\n\nThe next _q_ lines will contain 3 integers, describing a query in the format described in the statement.\n\nAll edge weights will be between 1 and 106.\n\n## Output\n\nFor each type 2 query, print the length of the shortest path in its own line.\n\n[samples]","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_span[n, q]（#cf_span[2 ≤ n, q ≤ 200 000]），分别表示节点数和查询数。\n\n接下来的 #cf_span[2n - 2] 行每行包含三个整数 #cf_span[ai, bi, ci]，表示一条从节点 #cf_span[ai] 指向节点 #cf_span[bi]、权重为 #cf_span[ci] 的有向边。\n\n其中前 #cf_span[n - 1] 行描述一棵以节点 #cf_span[1] 为根、边指向远离根方向的有根生成树；后 #cf_span[n - 1] 行满足 #cf_span[bi = 1]。\n\n更具体地：\n\n接下来的 #cf_span[q] 行每行包含三个整数，描述题目中所述格式的查询。\n\n所有边权均在 #cf_span[1] 到 #cf_span[106] 之间。\n\n对于每个类型 2 的查询，请在单独一行中输出最短路径的长度。\n\n## Input\n\n输入的第一行包含两个整数 #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] 之间。\n\n## Output\n\n对于每个类型 2 的查询，请在单独一行中输出最短路径的长度。\n\n[samples]","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 = E_1 \\cup E_2 $, with $ |E_1| = |E_2| = n - 1 $, so $ |E| = 2n - 2 $.  \n  - $ 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).  \n  - $ 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\\} $).  \n\nEach edge $ e = (u, v, w) \\in E $ has weight $ w \\in [1, 10^6] $.  \n\nLet $ 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\\} $:  \n- Type 1: Update the weight of edge $ e_k $ (identified by input order) to a new value.  \n- Type 2: Query the shortest path distance from node $ u_j $ to node $ v_j $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 200{,}000 $, $ 1 \\leq q \\leq 200{,}000 $.  \n2. All edge weights are integers in $ [1, 10^6] $.  \n3. The initial graph structure satisfies:  \n   - $ E_1 $ forms a directed tree rooted at 1 with all edges pointing away from 1.  \n   - $ E_2 $ consists of $ n-1 $ edges each pointing to node 1 (from some node $ \\neq 1 $).  \n4. For type 1 queries, the edge index refers to the input order of the $ 2n-2 $ edges.  \n5. For type 2 queries, $ u_j, v_j \\in V $.  \n\n**Objective**  \nFor 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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF838B","tags":["data structures","dfs and similar","trees"],"sample_group":[["5 9\n1 3 1\n3 2 2\n1 4 3\n3 5 4\n5 1 5\n3 1 6\n2 1 7\n4 1 8\n2 1 1\n2 1 3\n2 3 5\n2 5 2\n1 1 100\n2 1 3\n1 8 30\n2 4 2\n2 2 4","0\n1\n4\n8\n100\n132\n10"]],"created_at":"2026-03-03 11:00:39"}}