树剖10pts求调 感觉和书上代码已经没有差别了QAQ

HaloisAWA @ 2024-11-10 18:47:54

#include<bits/stdc++.h>
using namespace std;
int n,m,ut,vt,root,id[500010],num,ww[500010],op,a,b;
long long deep[500010],fa[500010],siz[500010],son[500010],top[500010];
long long tr[5000010],tag[5000010],P,w[500010],c;
vector<int> g[500010];
void build(int p,int pl,int pr) {
    if (pl == pr) {
        tr[p] = ww[pl] % P;
        return;
    }
    int mid = (pl + pr) >> 1;
    build(p << 1,pl,mid);
    build(p << 1 | 1,mid + 1,pr);
    tr[p] = (tr[p << 1] + tr[p << 1 | 1]) % P;
    return;
}
void addtag(int p,int pl,int pr,long long d) {
    tag[p] = (tag[p] + d) % P;
    tr[p] += (pr - pl + 1) * d % P;
    return;
}
int push_down(int p,int pl,int pr) {
    int mid = (pl + pr) >> 1;
    if (tag[p]) {
        addtag(p << 1,pl,mid,tag[p]);
        addtag(p << 1 | 1,mid + 1,pr,tag[p]);
        tag[p] = 0;
    }
    return mid;
}
void update(int p,int pl,int pr,int l,int r,long long d) {
    if (pl >= l && pr <= r) {
        addtag(p,pl,pr,d);
        return;
    }
    int mid = push_down(p,pl,pr);
    if (mid >= l) update(p << 1,pl,mid,l,r,d);
    if (mid < r) update(p << 1 | 1,mid + 1,pr,l,r,d);
    tr[p] = (tr[p << 1] + tr[p << 1 | 1]) % P;
    return;
}
long long query(int p,int pl,int pr,int l,int r) {
    if (pl >= l && pr <= r) return tr[p] % P;
    int mid = push_down(p,pl,pr);
    long long ret = 0;
    if (mid >= l) ret = (ret + query(p << 1,pl,mid,l,r)) % P;
    else ret = (ret + query(p << 1 | 1,mid + 1,pr,l,r)) % P;
    return ret;
}
void dfs1(int u,int father) {
    deep[u] = deep[father] + 1;
    fa[u] = father;
    siz[u] = 1;
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i];
        if (v != father) {
            dfs1(v,u);
            siz[u] += siz[v];
            if ((!son[u]) || siz[v] > siz[son[u]]) son[u] = v;
        }
    }
    return;
}
void dfs2(int u,int topu) {
    id[u] = ++ num;//
    ww[num] = w[u];//
    top[u] = topu;
    if (!son[u]) return;
    dfs2(son[u],topu);
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i];
        if (v != fa[u] && v != son[u]) dfs2(v,v);
    }
    return;
}
void update_range(int x,int y,long long d) {
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x,y);
        update(1,1,n,id[top[x]],id[x],d);
        x = fa[top[x]];
    }
    if (deep[x] < deep[y]) update(1,1,n,id[x],id[y],d);
    else update(1,1,n,id[y],id[x],d);
    return;
}
long long query_range(int x,int y) {
    long long res = 0;
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x,y);
        res = (res + query(1,1,n,id[top[x]],id[x])) % P;
        x = fa[top[x]];
    }
    if (deep[x] < deep[y]) res = (res + query(1,1,n,id[x],id[y])) % P;
    else res = (res + query(1,1,n,id[y],id[x])) % P;
    return res;
}
void update_tree(int x,long long d) {
    update(id[x],id[x] + siz[x] - 1,1,1,n,d);
    return;
}
long long query_tree(int x) {
    return query(id[x],id[x] + siz[x] - 1,1,1,n) % P;
}
int main() {
    scanf("%d%d%d%d",&n,&m,&root,&P);
    for (int i = 1;i <= n;i ++)
        scanf("%lld",&w[i]);
    for (int i = 1;i <= n - 1;i ++) {
        scanf("%d%d",&ut,&vt);
        g[ut].push_back(vt);
        g[vt].push_back(ut);
    }
    dfs1(root,0);
    dfs2(root,root);
    build(1,1,n);
    for (int i = 1;i <= m;i ++) {
        scanf("%d",&op);
        switch (op) {
            case 1:
                scanf("%d%d%lld",&a,&b,&c);
                update_range(a,b,c);
                break;
            case 2:
                scanf("%d%d",&a,&b);
                printf("%lld\n",query_range(a,b));
                break;
            case 3:
                scanf("%d%lld",&a,&c);
                update_tree(a,c);
                break;
            case 4:
                scanf("%d",&a);
                printf("%lld\n",query_tree(a));
                break;
        }
    }
    return 0;
}

by lg15166366290 @ 2024-11-10 19:07:16

#include<bits/stdc++.h>
using namespace std;
int n,m,ut,vt,root,id[500010],num,ww[500010],op,a,b;
long long deep[500010],fa[500010],siz[500010],son[500010],top[500010];
long long tr[5000010],tag[5000010],P,w[500010],c;
vector<int> g[500010];
void build(int p,int pl,int pr) {
    if (pl == pr) {
        tr[p] = ww[pl] % P;
        return;
    }
    int mid = (pl + pr) >> 1;
    build(p << 1,pl,mid);
    build(p << 1 | 1,mid + 1,pr);
    tr[p] = (tr[p << 1] + tr[p << 1 | 1]) % P;
    return;
}
void addtag(int p,int pl,int pr,long long d) {
    tag[p] = (tag[p] + d) % P;
    tr[p] = (tr[p] + (pr - pl + 1) * d) % P;
    return;
}
int push_down(int p,int pl,int pr) {
    int mid = (pl + pr) >> 1;
    if (tag[p]) {
        addtag(p << 1,pl,mid,tag[p]);
        addtag(p << 1 | 1,mid + 1,pr,tag[p]);
        tag[p] = 0;
    }
    return mid;
}
void update(int p,int pl,int pr,int l,int r,long long d) {
    if (pl >= l && pr <= r) {
        addtag(p,pl,pr,d);
        return;
    }
    int mid = push_down(p,pl,pr);
    if (mid >= l) update(p << 1,pl,mid,l,r,d);
    if (mid < r) update(p << 1 | 1,mid + 1,pr,l,r,d);
    tr[p] = (tr[p << 1] + tr[p << 1 | 1]) % P;
    return;
}
long long query(int p,int pl,int pr,int l,int r) {
    if (pl >= l && pr <= r) return tr[p] % P;
    int mid = push_down(p,pl,pr);
    long long ret = 0;
    if (mid >= l) ret = (ret + query(p << 1,pl,mid,l,r)) % P;
    if (mid < r) ret = (ret + query(p << 1 | 1,mid + 1,pr,l,r)) % P;
    return ret;
}
void dfs1(int u,int father) {
    deep[u] = deep[father] + 1;
    fa[u] = father;
    siz[u] = 1;
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i];
        if (v != father) {
            dfs1(v,u);
            siz[u] += siz[v];
            if ((!son[u]) || siz[v] > siz[son[u]]) son[u] = v;
        }
    }
    return;
}
void dfs2(int u,int topu) {
    id[u] = ++ num;//
    ww[num] = w[u];//
    top[u] = topu;
    if (!son[u]) return;
    dfs2(son[u],topu);
    for (int i = 0;i < g[u].size();i ++) {
        int v = g[u][i];
        if (v != fa[u] && v != son[u]) dfs2(v,v);
    }
    return;
}
void update_range(int x,int y,long long d) {
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x,y);
        update(1,1,n,id[top[x]],id[x],d);
        x = fa[top[x]];
    }
    if (deep[x] < deep[y]) update(1,1,n,id[x],id[y],d);
    else update(1,1,n,id[y],id[x],d);
    return;
}
long long query_range(int x,int y) {
    long long res = 0;
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x,y);
        res = (res + query(1,1,n,id[top[x]],id[x])) % P;
        x = fa[top[x]];
    }
    if (deep[x] < deep[y]) res = (res + query(1,1,n,id[x],id[y])) % P;
    else res = (res + query(1,1,n,id[y],id[x])) % P;
    return res;
}
void update_tree(int x,long long d) {
    update(1,1,n,id[x],id[x] + siz[x] - 1,d);
    return;
}
long long query_tree(int x) {
    return query(1,1,n,id[x],id[x] + siz[x] - 1) % P;
}
int main() {
    scanf("%d%d%d%d",&n,&m,&root,&P);
    for (int i = 1;i <= n;i ++)
        scanf("%lld",&w[i]);
    for (int i = 1;i <= n - 1;i ++) {
        scanf("%d%d",&ut,&vt);
        g[ut].push_back(vt);
        g[vt].push_back(ut);
    }
    dfs1(root,0);
    dfs2(root,root);
    build(1,1,n);
    for (int i = 1;i <= m;i ++) {
        scanf("%d",&op);
        switch (op) {
            case 1:
                scanf("%d%d%lld",&a,&b,&c);
                update_range(a,b,c);
                break;
            case 2:
                scanf("%d%d",&a,&b);
                printf("%lld\n",query_range(a,b));
                break;
            case 3:
                scanf("%d%lld",&a,&c);
                update_tree(a,c);
                break;
            case 4:
                scanf("%d",&a);
                printf("%lld\n",query_tree(a));
                break;
        }
    }
    return 0;
}

by lg15166366290 @ 2024-11-10 19:07:37

改好了 @HaloisAWA

by HaloisAWA @ 2024-11-10 19:22:02

@lg15166366290 跪谢巨佬QAQ 竟然一下子发现了我所有错误AWA