E. Jamie and Tree

[{"iden":"statement","content":"_让你惊讶的是，Jamie 是最终Boss！Ehehehe。_\n\nJamie 给了你一棵包含 #cf_span[n] 个顶点的树，顶点编号从 #cf_span[1] 到 #cf_span[n]。初始时，树的根是编号为 #cf_span[1] 的顶点。此外，每个顶点都有一个值。\n\nJamie 还给出了三种对树的操作：\n\n#cf_span[1 v] — 将树的根改为编号为 #cf_span[v] 的顶点。\n\n#cf_span[2 u v x] — 对包含 #cf_span[u] 和 #cf_span[v] 的最小子树中的每个顶点，将其值增加 #cf_span[x]。\n\n#cf_span[3 v] — 求编号为 #cf_span[v] 的顶点的子树中所有顶点的值之和。\n\n顶点 #cf_span[v] 的子树定义为满足从该顶点到树根的最短路径上经过 #cf_span[v] 的所有顶点构成的集合。请注意，改变树的根后，某个顶点的子树可能会发生变化。\n\n通过准确执行这些操作来向 Jamie 展示你的编程实力吧！\n\n输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5]）—— 分别表示树中的顶点数和需要处理的查询数。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 10^8 ≤ ai ≤ 10^8]）—— 表示顶点的初始值。\n\n接下来的 #cf_span[n - 1] 行，每行包含两个用空格分隔的整数 #cf_span[ui, vi]（#cf_span[1 ≤ ui, vi ≤ n]），描述树中顶点 #cf_span[ui] 和 #cf_span[vi] 之间的边。\n\n接下来的 #cf_span[q] 行描述查询。\n\n每个查询根据其类型具有以下格式之一：\n\n#cf_span[1 v]（#cf_span[1 ≤ v ≤ n]）用于第一类查询。\n\n#cf_span[2 u v x]（#cf_span[1 ≤ u, v ≤ n,  - 10^8 ≤ x ≤ 10^8]）用于第二类查询。\n\n#cf_span[3 v]（#cf_span[1 ≤ v ≤ n]）用于第三类查询。\n\n查询描述中的所有数字均为整数。\n\n查询必须按给定顺序执行。保证树是合法的。\n\n对于每个第三类查询，请输出所需答案。保证 Jamie 至少给出一个第三类查询。\n\n下图展示了第一个样例中查询后树的变化情况。\n\n"},{"iden":"input","content":"输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5]）—— 分别表示树中的顶点数和需要处理的查询数。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 10^8 ≤ ai ≤ 10^8]）—— 表示顶点的初始值。接下来的 #cf_span[n - 1] 行，每行包含两个用空格分隔的整数 #cf_span[ui, vi]（#cf_span[1 ≤ ui, vi ≤ n]），描述树中顶点 #cf_span[ui] 和 #cf_span[vi] 之间的边。接下来的 #cf_span[q] 行描述查询。每个查询根据其类型具有以下格式之一：#cf_span[1 v]（#cf_span[1 ≤ v ≤ n]）用于第一类查询。#cf_span[2 u v x]（#cf_span[1 ≤ u, v ≤ n,  - 10^8 ≤ x ≤ 10^8]）用于第二类查询。#cf_span[3 v]（#cf_span[1 ≤ v ≤ n]）用于第三类查询。查询描述中的所有数字均为整数。查询必须按给定顺序执行。保证树是合法的。"},{"iden":"output","content":"对于每个第三类查询，请输出所需答案。保证 Jamie 至少给出一个第三类查询。"},{"iden":"examples","content":"输入\n6 7\n1 4 2 8 5 7\n1 2\n3 1\n4 3\n4 5\n3 6\n3 1\n2 4 6 3\n3 4\n1 6\n2 2 4 -5\n1 4\n3 3\n输出\n27\n19\n5\n\n输入\n4 6\n4 3 5 6\n1 2\n2 3\n3 4\n3 1\n1 3\n2 2 4 3\n1 1\n2 2 4 -3\n3 1\n输出\n18\n21"},{"iden":"note","content":"下图展示了第一个样例中查询后树的变化情况。 "}] [{"iden":"statement","content":"_让你惊讶的是，Jamie 是最终Boss！Ehehehe。_\n\nJamie 给了你一棵包含 #cf_span[n] 个顶点的树，顶点编号从 #cf_span[1] 到 #cf_span[n]。初始时，树的根是编号为 #cf_span[1] 的顶点。此外，每个顶点都有一个值。\n\nJamie 还给出了三种对树的操作：\n\n#cf_span[1 v] — 将树的根改为编号为 #cf_span[v] 的顶点。\n\n#cf_span[2 u v x] — 对包含 #cf_span[u] 和 #cf_span[v] 的最小子树中的每个顶点，将其值增加 #cf_span[x]。\n\n#cf_span[3 v] — 求编号为 #cf_span[v] 的顶点的子树中所有顶点的值之和。\n\n顶点 #cf_span[v] 的子树定义为满足从该顶点到树根的最短路径上经过 #cf_span[v] 的所有顶点构成的集合。请注意，改变树的根后，某个顶点的子树可能会发生变化。\n\n通过准确执行这些操作来向 Jamie 展示你的编程实力吧！\n\n输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5]）—— 分别表示树中的顶点数和需要处理的查询数。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 10^8 ≤ ai ≤ 10^8]）—— 表示顶点的初始值。\n\n接下来的 #cf_span[n - 1] 行，每行包含两个用空格分隔的整数 #cf_span[ui, vi]（#cf_span[1 ≤ ui, vi ≤ n]），描述树中顶点 #cf_span[ui] 和 #cf_span[vi] 之间的边。\n\n接下来的 #cf_span[q] 行描述查询。\n\n每个查询根据其类型具有以下格式之一：\n\n#cf_span[1 v]（#cf_span[1 ≤ v ≤ n]）用于第一类查询。\n\n#cf_span[2 u v x]（#cf_span[1 ≤ u, v ≤ n,  - 10^8 ≤ x ≤ 10^8]）用于第二类查询。\n\n#cf_span[3 v]（#cf_span[1 ≤ v ≤ n]）用于第三类查询。\n\n查询描述中的所有数字均为整数。\n\n查询必须按给定顺序执行。保证树是合法的。\n\n对于每个第三类查询，请输出所需答案。保证 Jamie 至少给出一个第三类查询。\n\n下图展示了第一个样例中查询后树的变化情况。\n\n"},{"iden":"input","content":"输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5]）—— 分别表示树中的顶点数和需要处理的查询数。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 10^8 ≤ ai ≤ 10^8]）—— 表示顶点的初始值。接下来的 #cf_span[n - 1] 行，每行包含两个用空格分隔的整数 #cf_span[ui, vi]（#cf_span[1 ≤ ui, vi ≤ n]），描述树中顶点 #cf_span[ui] 和 #cf_span[vi] 之间的边。接下来的 #cf_span[q] 行描述查询。每个查询根据其类型具有以下格式之一：#cf_span[1 v]（#cf_span[1 ≤ v ≤ n]）用于第一类查询。#cf_span[2 u v x]（#cf_span[1 ≤ u, v ≤ n,  - 10^8 ≤ x ≤ 10^8]）用于第二类查询。#cf_span[3 v]（#cf_span[1 ≤ v ≤ n]）用于第三类查询。查询描述中的所有数字均为整数。查询必须按给定顺序执行。保证树是合法的。"},{"iden":"output","content":"对于每个第三类查询，请输出所需答案。保证 Jamie 至少给出一个第三类查询。"},{"iden":"examples","content":"输入\n6 7\n1 4 2 8 5 7\n1 2\n3 1\n4 3\n4 5\n3 6\n3 1\n2 4 6 3\n3 4\n1 6\n2 2 4 -5\n1 4\n3 3\n输出\n27\n19\n5\n\n输入\n4 6\n4 3 5 6\n1 2\n2 3\n3 4\n3 1\n1 3\n2 2 4 3\n1 1\n2 2 4 -3\n3 1\n输出\n18\n21"},{"iden":"note","content":"下图展示了第一个样例中查询后树的变化情况。 "}]

Let $ T = (V, E) $ be a tree with $ n $ vertices, where $ V = \{1, 2, \dots, n\} $. Let $ r \in V $ denote the current root of the tree, initially $ r = 1 $. Each vertex $ v \in V $ has an associated value $ a_v \in \mathbb{Z} $, initialized as given. Define for any vertex $ v \in V $ and current root $ r $, the **subtree of $ v $** as the set of all vertices $ u \in V $ such that the unique simple path from $ u $ to $ r $ passes through $ v $. Equivalently, it is the connected component containing $ v $ in the tree after removing the edge from $ v $ to its parent in the rooted tree (with root $ r $). For any two vertices $ u, v \in V $, define $ \text{path}(u, v) $ as the unique simple path between $ u $ and $ v $ in the unrooted tree. Define $ \text{min\_subtree}(u, v) $ as the smallest subtree (under the current root $ r $) that contains both $ u $ and $ v $. This is equivalent to the union of all vertices lying on the unique simple path between $ u $ and $ v $, together with all subtrees rooted at vertices along that path (in the current rooted tree). Equivalently, $ \text{min\_subtree}(u, v) $ is the subtree rooted at the lowest common ancestor (LCA) of $ u $ and $ v $ **in the current rooted tree**, and extending to include both $ u $ and $ v $ — i.e., it is the subtree rooted at $ \text{LCA}_r(u, v) $ that contains both $ u $ and $ v $. --- **Given:** - $ n, q \in \mathbb{Z}^+ $, $ 1 \leq n, q \leq 10^5 $ - Initial values: $ a = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ - Tree structure: $ n-1 $ edges forming a tree - Current root: $ r \leftarrow 1 $ - Three types of queries: --- **Operations:** 1. **Update root**: $ r \leftarrow v $ 2. **Range update on min-subtree**: Let $ w = \text{LCA}_r(u, v) $. Let $ S = \text{subtree}(w) \cap \{ \text{vertices on the path from } u \text{ to } v \text{ and their descendants in the rooted tree} \} $. Then: $$ \forall z \in S,\quad a_z \leftarrow a_z + x $$ 3. **Subtree sum query**: Let $ S = \text{subtree}(v) $ under current root $ r $. Output: $$ \sum_{z \in S} a_z $$ --- **Constraints:** - All operations must be performed in order. - The tree is static; only the root and vertex values change. - For LCA computations, the tree is re-rooted dynamically; LCA must be computed with respect to the current root $ r $. --- **Formal Goal:** Process $ q $ queries of types 1, 2, 3 as defined above, and for each type-3 query, output the sum of values in the current subtree of $ v $ under the current root $ r $.