//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "树链剖分+MOD": {
        "prefix": "acm-4.2shulianpoufenMOD",
        "body": [
            "const int MAXN = 1e5 + 5;  // 最大节点数",
            "int N, M, R, P;  // 节点数、操作数、根节点、模数",
            "vector<int> adj[MAXN];  // 邻接表存储树结构",
            "int val[MAXN];  // 节点初始权值",
            "",
            "// 树链剖分相关变量",
            "int parent[MAXN];  // 父节点",
            "int depth[MAXN];   // 节点深度",
            "int sz[MAXN];      // 子树大小",
            "int heavy[MAXN];   // 重儿子",
            "int pos[MAXN];     // 节点在线段树中的位置",
            "int top[MAXN];     // 所在重链的顶部节点",
            "int current_pos;   // 当前DFS序位置",
            "",
            "// 线段树节点结构",
            "struct node {",
            "    int data;  // 节点值",
            "    int lazy;  // 懒标记",
            "    node() : data(0), lazy(0) {}",
            "};",
            "",
            "vector<node> tree;  // 线段树",
            "",
            "// 构建线段树",
            "void build(const vector<int>& datas, vector<node>& tree, int rt, int left, int right) {",
            "    if (left == right) {",
            "        tree[rt].data = datas[left];",
            "        return;",
            "    }",
            "    int mid = left + (right - left) / 2;",
            "    build(datas, tree, 2 * rt, left, mid);",
            "    build(datas, tree, 2 * rt + 1, mid + 1, right);",
            "    tree[rt].data = (tree[2 * rt].data + tree[2 * rt + 1].data) % P;",
            "}",
            "",
            "// 下传懒标记",
            "void pushDown(vector<node>& tree, int rt, int len) {",
            "    if (tree[rt].lazy != 0) {",
            "        tree[rt * 2].data = (tree[rt * 2].data + tree[rt].lazy * (len - len / 2)) % P;",
            "        tree[rt * 2].lazy = (tree[rt * 2].lazy + tree[rt].lazy) % P;",
            "        tree[rt * 2 + 1].data = (tree[rt * 2 + 1].data + tree[rt].lazy * (len / 2)) % P;",
            "        tree[rt * 2 + 1].lazy = (tree[rt * 2 + 1].lazy + tree[rt].lazy) % P;",
            "        tree[rt].lazy = 0;",
            "    }",
            "}",
            "",
            "// 线段树区间查询",
            "int query(vector<node>& tree, int rt, int left, int right, int ql, int qr) {",
            "    if (ql > right || qr < left) {",
            "        return 0;",
            "    }",
            "    if (ql <= left && qr >= right) {",
            "        return tree[rt].data;",
            "    }",
            "    pushDown(tree, rt, right - left + 1);",
            "    int mid = left + (right - left) / 2;",
            "    int leftsum = query(tree, 2 * rt, left, mid, ql, qr);",
            "    int rightsum = query(tree, 2 * rt + 1, mid + 1, right, ql, qr);",
            "    return (leftsum + rightsum) % P;",
            "}",
            "",
            "// 线段树区间更新",
            "void updateRange(vector<node>& tree, int rt, int left, int right, int ul, int ur, int value) {",
            "    if (ul > right || ur < left) return;",
            "    if (ul <= left && ur >= right) {",
            "        tree[rt].data = (tree[rt].data + value * (right - left + 1)) % P;",
            "        tree[rt].lazy = (tree[rt].lazy + value) % P;",
            "        return;",
            "    }",
            "    pushDown(tree, rt, right - left + 1);",
            "    int mid = left + (right - left) / 2;",
            "    updateRange(tree, 2 * rt, left, mid, ul, ur, value);",
            "    updateRange(tree, 2 * rt + 1, mid + 1, right, ul, ur, value);",
            "    tree[rt].data = (tree[2 * rt].data + tree[2 * rt + 1].data) % P;",
            "}",
            "",
            "// 第一次DFS：计算父节点、深度、子树大小和重儿子",
            "void dfs1(int u, int p) {",
            "    parent[u] = p;",
            "    depth[u] = depth[p] + 1;",
            "    sz[u] = 1;",
            "    heavy[u] = 0;",
            "    for (int v : adj[u]) {",
            "        if (v != p) {",
            "            dfs1(v, u);",
            "            sz[u] += sz[v];",
            "            if (sz[v] > sz[heavy[u]]) {",
            "                heavy[u] = v;",
            "            }",
            "        }",
            "    }",
            "}",
            "",
            "// 第二次DFS：进行重链剖分，计算DFS序和重链顶部",
            "void dfs2(int u, int p, int chain_top) {",
            "    pos[u] = ++current_pos;",
            "    top[u] = chain_top;",
            "    if (heavy[u]) {",
            "        dfs2(heavy[u], u, chain_top);",
            "    }",
            "    for (int v : adj[u]) {",
            "        if (v != p && v != heavy[u]) {",
            "            dfs2(v, u, v);",
            "        }",
            "    }",
            "}",
            "",
            "// 路径更新：将x到y路径上的节点值都加上z",
            "void pathUpdate(int x, int y, int z) {",
            "    while (top[x] != top[y]) {",
            "        if (depth[top[x]] > depth[top[y]]) {",
            "            swap(x, y);",
            "        }",
            "        updateRange(tree, 1, 1, N, pos[top[y]], pos[y], z);",
            "        y = parent[top[y]];",
            "    }",
            "    if (depth[x] > depth[y]) {",
            "        swap(x, y);",
            "    }",
            "    updateRange(tree, 1, 1, N, pos[x], pos[y], z);",
            "}",
            "",
            "// 路径查询：查询x到y路径上的节点值之和",
            "int pathQuery(int x, int y) {",
            "    int res = 0;",
            "    while (top[x] != top[y]) {",
            "        if (depth[top[x]] > depth[top[y]]) {",
            "            swap(x, y);",
            "        }",
            "        res = (res + query(tree, 1, 1, N, pos[top[y]], pos[y])) % P;",
            "        y = parent[top[y]];",
            "    }",
            "    if (depth[x] > depth[y]) {",
            "        swap(x, y);",
            "    }",
            "    res = (res + query(tree, 1, 1, N, pos[x], pos[y])) % P;",
            "    return res;",
            "}",
            "",
            "// 子树更新：将以x为根的子树所有节点值加上z",
            "void subtreeUpdate(int x, int z) {",
            "    int l = pos[x];",
            "    int r = pos[x] + sz[x] - 1;",
            "    updateRange(tree, 1, 1, N, l, r, z);",
            "}",
            "",
            "// 子树查询：查询以x为根的子树所有节点值之和",
            "int subtreeQuery(int x) {",
            "    int l = pos[x];",
            "    int r = pos[x] + sz[x] - 1;",
            "    return query(tree, 1, 1, N, l, r);",
            "}",
            "",
            "// 求两个节点的最近公共祖先（LCA）",
            "int lca(int x, int y) {",
            "    while (top[x] != top[y]) {",
            "        if (depth[top[x]] < depth[top[y]]) {",
            "            swap(x, y);",
            "        }",
            "        x = parent[top[x]];",
            "    }",
            "    return depth[x] < depth[y] ? x : y;",
            "}",
            "",
            "int main() {",
            "    ios::sync_with_stdio(false);",
            "    cin.tie(nullptr);",
            "",
            "    cin >> N >> M >> R >> P;",
            "    for (int i = 1; i <= N; ++i) {",
            "        cin >> val[i];",
            "    }",
            "    for (int i = 1; i < N; ++i) {",
            "        int x, y;",
            "        cin >> x >> y;",
            "        adj[x].push_back(y);",
            "        adj[y].push_back(x);",
            "    }",
            "",
            "    // 第一次DFS预处理",
            "    dfs1(R, 0);",
            "    current_pos = 0;",
            "    // 第二次DFS进行重链剖分",
            "    dfs2(R, 0, R);",
            "",
            "    // 构建线段树",
            "    vector<int> datas(N + 1);",
            "    for (int i = 1; i <= N; ++i) {",
            "        datas[pos[i]] = val[i] % P;",
            "    }",
            "",
            "    tree.resize(4 * (N + 1));",
            "    build(datas, tree, 1, 1, N);",
            "",
            "    // 处理操作",
            "    while (M--) {",
            "        int cmd;",
            "        cin >> cmd;",
            "        if (cmd == 1) {  // 路径更新",
            "            int x, y, z;",
            "            cin >> x >> y >> z;",
            "            pathUpdate(x, y, z);",
            "        } else if (cmd == 2) {  // 路径查询",
            "            int x, y;",
            "            cin >> x >> y;",
            "            cout << pathQuery(x, y) << '\\n';",
            "        } else if (cmd == 3) {  // 子树更新",
            "            int x, z;",
            "            cin >> x >> z;",
            "            subtreeUpdate(x, z);",
            "        } else if (cmd == 4) {  // 子树查询",
            "            int x;",
            "            cin >> x;",
            "            cout << subtreeQuery(x) << '\\n';",
            "        }",
            "    }",
            "",
            "    return 0;",
            "}"
        ],
        "description": "插入 树链剖分+MOD"
    }
}