{"problem":{"name":"E. Jamie and Tree","description":{"content":"_To your surprise, Jamie is the final boss! Ehehehe._ Jamie has given you a tree with _n_ vertices, numbered from 1 to _n_. Initially, the root of the tree is the vertex with number 1. Also, each ver","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF916E"},"statements":[{"statement_type":"Markdown","content":"_To your surprise, Jamie is the final boss! Ehehehe._\n\nJamie has given you a tree with _n_ vertices, numbered from 1 to _n_. Initially, the root of the tree is the vertex with number 1. Also, each vertex has a value on it.\n\nJamie also gives you three types of queries on the tree:\n\n1 _v_ — Change the tree's root to vertex with number _v_.\n\n2 _u_ _v_ _x_ — For each vertex in the subtree of smallest size that contains _u_ and _v_, add _x_ to its value.\n\n3 _v_ — Find sum of values of vertices in the subtree of vertex with number _v_.\n\nA subtree of vertex _v_ is a set of vertices such that _v_ lies on shortest path from this vertex to root of the tree. Pay attention that subtree of a vertex can change after changing the tree's root.\n\nShow your strength in programming to Jamie by performing the queries accurately!\n\n## Input\n\nThe first line of input contains two space-separated integers _n_ and _q_ (1 ≤ _n_ ≤ 105, 1 ≤ _q_ ≤ 105) — the number of vertices in the tree and the number of queries to process respectively.\n\nThe second line contains _n_ space-separated integers _a_1, _a_2, ..., _a__n_ ( - 108 ≤ _a__i_ ≤ 108) — initial values of the vertices.\n\nNext _n_ - 1 lines contains two space-separated integers _u__i_, _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_) describing edge between vertices _u__i_ and _v__i_ in the tree.\n\nThe following _q_ lines describe the queries.\n\nEach query has one of following formats depending on its type:\n\n1 _v_ (1 ≤ _v_ ≤ _n_) for queries of the first type.\n\n2 _u_ _v_ _x_ (1 ≤ _u_, _v_ ≤ _n_,  - 108 ≤ _x_ ≤ 108) for queries of the second type.\n\n3 _v_ (1 ≤ _v_ ≤ _n_) for queries of the third type.\n\nAll numbers in queries' descriptions are integers.\n\nThe queries must be carried out in the given order. It is guaranteed that the tree is valid.\n\n## Output\n\nFor each query of the third type, output the required answer. It is guaranteed that at least one query of the third type is given by Jamie.\n\n[samples]\n\n## Note\n\nThe following picture shows how the tree varies after the queries in the first sample.\n\n<center>![image](https://espresso.codeforces.com/6ec243c9d34a8b628cfad6c9cf4d01e24b1219f1.png)</center>","is_translate":false,"language":"English"},{"statement_type":"Markdown","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\":\"下图展示了第一个样例中查询后树的变化情况。   \"}]\n\n[{\"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\":\"下图展示了第一个样例中查询后树的变化情况。   \"}]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","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.\n\nDefine 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 $).\n\nFor 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).\n\nEquivalently, $ \\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 $.\n\n---\n\n**Given:**\n\n- $ n, q \\in \\mathbb{Z}^+ $, $ 1 \\leq n, q \\leq 10^5 $\n- Initial values: $ a = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $\n- Tree structure: $ n-1 $ edges forming a tree\n- Current root: $ r \\leftarrow 1 $\n- Three types of queries:\n\n---\n\n**Operations:**\n\n1. **Update root**:  \n   $ r \\leftarrow v $\n\n2. **Range update on min-subtree**:  \n   Let $ w = \\text{LCA}_r(u, v) $.  \n   Let $ S = \\text{subtree}(w) \\cap \\{ \\text{vertices on the path from } u \\text{ to } v \\text{ and their descendants in the rooted tree} \\} $.  \n   Then:  \n   $$\n   \\forall z \\in S,\\quad a_z \\leftarrow a_z + x\n   $$\n\n3. **Subtree sum query**:  \n   Let $ S = \\text{subtree}(v) $ under current root $ r $.  \n   Output:\n   $$\n   \\sum_{z \\in S} a_z\n   $$\n\n---\n\n**Constraints:**\n\n- All operations must be performed in order.\n- The tree is static; only the root and vertex values change.\n- For LCA computations, the tree is re-rooted dynamically; LCA must be computed with respect to the current root $ r $.\n\n---\n\n**Formal Goal:**\n\nProcess $ 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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF916E","tags":["data structures","trees"],"sample_group":[["6 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","27\n19\n5"],["4 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","18\n21"]],"created_at":"2026-03-03 11:00:39"}}