样例没过，求调错

LiuTianyou @ 2023-01-31 19:24:53

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<list<int> > tree;
int n, m, r, p;
int val[100005], depth[100005], father[100005], siz[100005], son[100005];
int dfn[100005], top[100005], nval[100005], cnt = 0;
struct SegmentTree{
    struct node{
        int left, right;
        int sum, lazytag;
    }tree[100005];
    void pushdown(int p){
        if(tree[p].lazytag){
            tree[p * 2].sum += tree[p].lazytag * (tree[p * 2].right - tree[p * 2].left + 1) % p;
            tree[p * 2 + 1].sum += tree[p].lazytag * (tree[p * 2 + 1].right - tree[p * 2 + 1].left + 1) % p;
            tree[p * 2].lazytag += tree[p].lazytag;
            tree[p * 2 + 1].lazytag += tree[p].lazytag;
            tree[p].lazytag = 0;
        }
    }
    void build(int p, int l, int r){
        tree[p].left = l, tree[p].right = r;
        if(l == r){
            tree[p].sum = nval[l] % p;
            return;
        }
        int mid = (l + r) / 2;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
        tree[p].sum = (tree[p * 2].sum + tree[p * 2 + 1].sum) % p;
        return;
    }
    void add(int p, int l, int r, int v){
        if(l <= tree[p].left && tree[p].right <= r){
            tree[p].lazytag = (tree[p].lazytag + v) % p;
            tree[p].sum = (tree[p].sum + v * (tree[p].right - tree[p].left + 1)) % p;
            return;
        }
        pushdown(p);
        int mid = (tree[p].left + tree[p].right) / 2;
        if(l <= mid) add(p * 2, l, r, v);
        if(r > mid) add(p * 2 + 1, l, r, v);
        tree[p].sum = (tree[p * 2].sum + tree[p * 2 + 1].sum) % p;
        return;
    }
    int query(int p, int l, int r){
        if(l <= tree[p].left && tree[p].right <= r){
            return tree[p].sum;
        }
        pushdown(p);
        int mid = (tree[p].left + tree[p].right) / 2, ret = 0;
        if(l <= mid) ret += query(p * 2, l, r);
        if(r > mid) ret += query(p * 2 + 1, l, r);
        return ret % p;
    }
}STree;
void dfs1(int x, int fa){
    int maxson = -1;
    depth[x] = depth[fa] + 1, father[x] = fa, siz[x] = 1;
    for(auto it = tree[x].begin(); it != tree[x].end(); it++){
        if(*it != fa){
            dfs1(*it, x);
            siz[x] += siz[*it];
            if(siz[*it] > maxson) son[x] = *it, maxson = siz[*it];
        }
    }
}
void dfs2(int x, int topf){
    dfn[x] = ++cnt, nval[cnt] = val[x], top[x] = topf;
    if(son[x] == 0) return;
    dfs2(son[x], topf);
    for(auto it = tree[x].begin(); it != tree[x].end(); it++){
        if(*it == father[x] || *it == son[x]) continue;
        dfs2(*it, *it);
    }
}
signed main(){
    scanf("%lld %lld %lld %lld", &n, &m, &r, &p);
    tree.resize(n + 1);
    for(int i = 1; i <= n; i++) scanf("%lld", &val[i]);
    for(int i = 1, x, y; i <= n - 1; i++){
        scanf("%lld %lld", &x, &y);
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    dfs1(r, 0);
    dfs2(r, r);
    STree.build(1, 1, n);
    while(m--){
        int op, x, y, z;
        scanf("%lld", &op);
        if(op == 1){
            scanf("%lld %lld %lld", &x, &y, &z);
            z %= p;
            while(top[x] != top[y]){
                if(depth[top[x]] < depth[top[y]]) swap(x, y);
                STree.add(1, dfn[top[x]], dfn[x], z);
                x = father[top[x]];
            }
            if(depth[x] < depth[y]) swap(x, y);
            STree.add(1, dfn[x], dfn[y], z);
        }else if(op == 2){
            int ans = 0;
            scanf("%lld %lld", &x, &y);
            while(top[x] != top[y]){
                if(depth[top[x]] < depth[top[y]]) swap(x, y);
                ans = (ans + STree.query(1, dfn[top[x]], dfn[x])) % p;
                x = father[top[x]];
            }
            if(depth[x] < depth[y]) swap(x, y);
            ans = (ans + STree.query(1, dfn[x], dfn[y])) % p;
            printf("%lld\n", ans);
        }else if(op == 3){
            scanf("%lld %lld", &x, &z);
            STree.add(1, dfn[x], dfn[x] + siz[x] - 1, z);
        }else{
            scanf("%lld", &x);
            printf("%lld\n", STree.query(1, dfn[x], dfn[x] + siz[x] - 1));
        }
    }
    return 0;
}

by 幻想繁星 @ 2023-01-31 19:41:40

@LiuTianyou 有人理你，但是这个人不会题呢

by MSqwq @ 2023-01-31 19:49:15

@LiuTianyou 线段树有问题，但还在找，别急

by poly @ 2023-01-31 19:49:59

对于很长的代码建议使用gdb呢

by LiuTianyou @ 2023-01-31 19:50:50

今天晚上没什么心情……拜托了

by MSqwq @ 2023-01-31 19:52:26

@LiuTianyou 有一个很典型的错误就是你的 p 在乱用，你以为是用的模数 p，其实是在用你线段树的节点

by LiuTianyou @ 2023-01-31 19:52:46

@MSqwq 谢谢你了，我要区分大小写

by LiuTianyou @ 2023-01-31 19:55:13

@MSqwq 然而似乎没用

by MSqwq @ 2023-01-31 19:56:39

@LiuTianyou 你先别急，快了

by LiuTianyou @ 2023-01-31 19:58:52

@MSqwq 你别急，我虽然时间不多，但是今晚还是有时间的

by MSqwq @ 2023-01-31 20:00:50

@LiuTianyou 过了
两个问题，线段树开小了，顶着开就是找死的
其次就是当你跳到重链上的时候

if(depth[x] > depth[y]) swap(x, y);

大于小于写反了，dep 越小，dfn 会越小
qwq注意一下的啦

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<list<int> > tree;
int n, m, r, P;
int val[400005], depth[400005], father[400005], siz[400005], son[400005];
int dfn[400005], top[400005], nval[400005], cnt = 0;
struct SegmentTree{
    struct node{
        int left, right;
        int sum, lazytag;
    }tree[400005];
    void pushdown(int p){
        if(tree[p].lazytag){
            tree[p * 2].sum += tree[p].lazytag * (tree[p * 2].right - tree[p * 2].left + 1) % P;
            tree[p * 2 + 1].sum += tree[p].lazytag * (tree[p * 2 + 1].right - tree[p * 2 + 1].left + 1) % P;
            tree[p * 2].lazytag += tree[p].lazytag;
            tree[p * 2 + 1].lazytag += tree[p].lazytag;
            tree[p].lazytag = 0;
        }
    }
    void build(int p, int l, int r){
        tree[p].left = l, tree[p].right = r;
        if(l == r){
            tree[p].sum = nval[l] % P;
            return;
        }
        int mid = (l + r) / 2;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
        tree[p].sum = (tree[p * 2].sum + tree[p * 2 + 1].sum) % P;
        return;
    }
    void add(int p, int l, int r, int v){
        if(l <= tree[p].left && tree[p].right <= r){
            tree[p].lazytag = (tree[p].lazytag + v) % P;
            tree[p].sum = (tree[p].sum + v * (tree[p].right - tree[p].left + 1)) % P;
            return;
        }
        pushdown(p);
        int mid = (tree[p].left + tree[p].right) / 2;
        if(l <= mid) add(p * 2, l, r, v);
        if(r > mid) add(p * 2 + 1, l, r, v);
        tree[p].sum = (tree[p * 2].sum + tree[p * 2 + 1].sum) % P;
        return;
    }
    int query(int p, int l, int r){
        if(l <= tree[p].left && tree[p].right <= r){
            return tree[p].sum;
        }
        pushdown(p);
        int mid = (tree[p].left + tree[p].right) / 2, ret = 0;
        if(l <= mid) ret += query(p * 2, l, r);
        if(r > mid) ret += query(p * 2 + 1, l, r);
        return ret % P;
    }
}STree;
void dfs1(int x, int fa){
    int maxson = -1;
    depth[x] = depth[fa] + 1, father[x] = fa, siz[x] = 1;
    for(auto it = tree[x].begin(); it != tree[x].end(); it++){
        if(*it != fa){
            dfs1(*it, x);
            siz[x] += siz[*it];
            if(siz[*it] > maxson) son[x] = *it, maxson = siz[*it];
        }
    }
}
void dfs2(int x, int topf){
    dfn[x] = ++cnt, nval[cnt] = val[x], top[x] = topf;
    if(son[x] == 0) return;
    dfs2(son[x], topf);
    for(auto it = tree[x].begin(); it != tree[x].end(); it++){
        if(*it == father[x] || *it == son[x]) continue;
        dfs2(*it, *it);
    }
}
signed main(){
    scanf("%lld %lld %lld %lld", &n, &m, &r, &P);
    tree.resize(n + 1);
    for(int i = 1; i <= n; i++) scanf("%lld", &val[i]);
    for(int i = 1, x, y; i <= n - 1; i++){
        scanf("%lld %lld", &x, &y);
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    dfs1(r, 0);
    dfs2(r, r);
    STree.build(1, 1, n);
    while(m--){
        int op, x, y, z;
        scanf("%lld", &op);
        if(op == 1){
            scanf("%lld %lld %lld", &x, &y, &z);
            z %= P;
            while(top[x] != top[y]){
                if(depth[top[x]] < depth[top[y]]) swap(x, y);
                STree.add(1, dfn[top[x]], dfn[x], z);
                x = father[top[x]];
            }
            if(depth[x] > depth[y]) swap(x, y);
            STree.add(1, dfn[x], dfn[y], z);
        }else if(op == 2){
            int ans = 0;
            scanf("%lld %lld", &x, &y);
            while(top[x] != top[y]){
                if(depth[top[x]] < depth[top[y]]) swap(x, y);
                ans = (ans + STree.query(1, dfn[top[x]], dfn[x])) % P;
                x = father[top[x]];
            }
            if(depth[x] > depth[y]) swap(x, y);
            ans = (ans + STree.query(1, dfn[x], dfn[y])) % P;
            printf("%lld\n", ans);
        }else if(op == 3){
            scanf("%lld %lld", &x, &z);
            STree.add(1, dfn[x], dfn[x] + siz[x] - 1, z);
        }else{
            scanf("%lld", &x);
            printf("%lld\n", STree.query(1, dfn[x], dfn[x] + siz[x] - 1));
        }
    }
    return 0;
}