重剖板子 WA 19pts 求调，玄关

liyixin0514 @ 2024-11-25 21:51:50

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace tree_pou_heavy {
    constexpr int N=1e5+7;
    int n,m,rt,p;
    int add(int a,int b) { return a+b>=p ? a+b-p : a+b; }
    void _add(int &a,int b) { a=add(a,b); }
    void _max(int &a,int b) { a=max(a,b); }
    int a[N];
    int u,v;
    struct edge {
        int to,ne;
    }e[N<<1];
    int head[N],e_cnt;
    void addedge(int u,int v) { e[++e_cnt] = {v, head[u]}; head[u]=e_cnt; }
    struct tree {
        int fa[N],dep[N],siz[N],gson[N];
        int st[30][N];
        int lcamin(int u,int v) { return dfn[u]<dfn[v] ? u : v; }
        int getlca(int u,int v) {
            if(u==v) return u;
            int mn=min(dfn[u],dfn[v])+1, mx=max(dfn[u],dfn[v]);
            int lg=__lg(mx-mn+1);
            return lcamin(st[lg][mn],st[lg][mx-(1<<lg)+1]);
        }
        int dfn[N],eddfn[N],cnt,idfn[N];
        int top[N];
        void dfs(int u,int f) {
            fa[u]=f;
            siz[u]=1;
            for(int i=head[u]; i; i=e[i].ne) {
                int v=e[i].to;
                if(v==f) continue;
                dfs(v,u);
                siz[u]+=siz[v];
                if(siz[v]>siz[gson[u]]) gson[u]=v;
            }
        }
        void dfs(int u) {
            dfn[u]=eddfn[u]=++cnt;
            idfn[cnt]=u;
            st[0][cnt]=fa[u];
            if(gson[u]) top[gson[u]]=top[u], dfs(gson[u]);
            _max(eddfn[u],eddfn[gson[u]]);
            for(int i=head[u]; i; i=e[i].ne) {
                int v=e[i].to;
                if(v==fa[u] || v==gson[u]) continue;
                top[v]=v, dfs(v);
                _max(eddfn[u],eddfn[v]);
                if(siz[v]>siz[gson[u]]) gson[u]=v;
            }
        }
        int tr[N<<2],tag[N<<2];
        int p;
        void build() {
            p=1;
            while(p-2<n) p<<=1;
            rep(i,1,n) tr[p+i]=a[idfn[i]];
            per(i,p-1,1) tr[i]=add(tr[i<<1],tr[i<<1|1]);
        }
        void init() {
            dfs(rt,0);
            // pf("gson "); rep(i,1,n) pf("%d ",gson[i]); pf("\n");
            top[rt]=rt;
            dfs(rt);
            // pf("dfn "); rep(i,1,n) pf("%d ",dfn[i]); pf("\n");
            // pf("eddfn "); rep(i,1,n) pf("%d ",eddfn[i]); pf("\n");
            // pf("top "); rep(i,1,n) pf("%d ",top[i]); pf("\n");
            int lg=__lg(n);
            rep(k,1,lg) for(int i=1;i+(1<<k)-1<=n;i++) st[k][i]=lcamin(st[k-1][i],st[k-1][i+(1<<(k-1))]);
            build();
        }
        void maketag(int u,int x,int siz) { _add(tr[u],1ll*x*siz%p), _add(tag[u],x); }
        void pushup(int u,int siz) { tr[u]=add(add(tr[u<<1],tr[u<<1|1]),1ll*siz*tag[u]); }
        void _update(int l,int r,int x) {
            l=p+l-1, r=p+r+1;
            int siz=1;
            while(l^r^1) {
                if((l&1)^1) maketag(l^1,x,siz);
                if(r&1) maketag(r^1,x,siz);
                l>>=1, r>>=1, siz<<=1;
                pushup(l,siz), pushup(r,siz);
            } 
            for(l>>=1, siz<<=1; l; l>>=1, siz<<=1) pushup(l,siz);
        }
        int _query(int l,int r) {
            l=p+l-1, r=p+r+1;
            int sizl=0,sizr=0,siz=1;
            int s=0;
            while(l^r^1) {
                if((l&1)^1) _add(s,tr[l^1]), sizl+=siz;
                if(r&1) _add(s,tr[r^1]), sizr+=siz;
                l>>=1, r>>=1, siz<<=1;
                _add(s,1ll*tag[l]*sizl%p), _add(s,1ll*tag[r]*sizr%p);
            }
            for(l>>=1, sizl+=sizr; l; l>>=1) _add(s,1ll*tag[l]*sizl%p);
            return s;
        }
        void update(int u,int v,int x) {
            int lca=getlca(u,v);
            // pf("%d %d %d\n",u,v,lca);
            while(dfn[top[u]]>dfn[lca]) _update(dfn[top[u]],dfn[u],x), u=fa[top[u]];
            _update(dfn[lca],dfn[u],x);
            while(dfn[top[v]]>dfn[lca]) _update(dfn[top[v]],dfn[v],x), v=fa[top[v]];
            if(dfn[v]>=dfn[lca]+1) _update(dfn[lca]+1,dfn[v],x);
        }
        void update(int u,int x) {
            _update(dfn[u],eddfn[u],x);
        }
        int query(int u,int v) {
            int lca=getlca(u,v);
            int s=0;
            while(dfn[top[u]]>dfn[lca]) _add(s,_query(dfn[top[u]],dfn[u])), u=fa[top[u]];
            _add(s,_query(dfn[lca],dfn[u]));
            while(dfn[top[v]]>dfn[lca]) _add(s,_query(dfn[top[v]],dfn[v])), v=fa[top[v]];
            if(dfn[v]>=dfn[lca]+1) _add(s,_query(dfn[lca]+1,dfn[v]));
            return s;
        }
        int query(int u) {
            return _query(dfn[u],eddfn[u]);
        }
        // void write() {
            // pf("tr "); rep(i,1,p+n) pf("%d ",tr[i]); pf("\n");
            // pf("tag "); rep(i,1,p+n) pf("%d ",tag[i]); pf("\n");
        // }
    }T;
    int op,x;
    void main() {
        sf("%d%d%d%d",&n,&m,&rt,&p);
        rep(i,1,n) sf("%d",&a[i]), a[i]%=p;
        rep(i,1,n-1) sf("%d%d",&u,&v), addedge(u,v), addedge(v,u);
        T.init();
        // T.write();
        rep(i,1,m) {
            sf("%d",&op);
            if(op==1) sf("%d%d%d",&u,&v,&x), T.update(u,v,x);
            else if(op==2) sf("%d%d",&u,&v), pf("%d\n",T.query(u,v));
            else if(op==3) sf("%d%d",&u,&x), T.update(u,x);
            else sf("%d",&u), pf("%d\n",T.query(u));
            // T.write();
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("my.out","w",stdout);
    #endif
    tree_pou_heavy :: main();
}

by liyixin0514 @ 2024-11-25 22:08:39

经过肉眼与 LCA 板子 和 zkw 线段树板子 的文本比对，LCA 和线段树应该是没有写错的，可能是重剖部分出了问题？但是我不知道哪里有问题 qwq

by liyixin0514 @ 2024-11-25 22:13:09

发现了一点很唐的不影响运行结果的东西，修改后代码如下：

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace tree_pou_heavy {
    constexpr int N=1e5+7;
    int n,m,rt,p;
    int add(int a,int b) { return a+b>=p ? a+b-p : a+b; }
    void _add(int &a,int b) { a=add(a,b); }
    void _max(int &a,int b) { a=max(a,b); }
    int a[N];
    int u,v;
    struct edge {
        int to,ne;
    }e[N<<1];
    int head[N],e_cnt;
    void addedge(int u,int v) { e[++e_cnt] = {v, head[u]}; head[u]=e_cnt; }
    struct tree {
        int fa[N],siz[N],gson[N];
        int st[30][N];
        int lcamin(int u,int v) { return dfn[u]<dfn[v] ? u : v; }
        int getlca(int u,int v) {
            if(u==v) return u;
            int mn=min(dfn[u],dfn[v])+1, mx=max(dfn[u],dfn[v]);
            int lg=__lg(mx-mn+1);
            return lcamin(st[lg][mn],st[lg][mx-(1<<lg)+1]);
        }
        int dfn[N],eddfn[N],cnt,idfn[N];
        int top[N];
        void dfs(int u,int f) {
            fa[u]=f;
            siz[u]=1;
            for(int i=head[u]; i; i=e[i].ne) {
                int v=e[i].to;
                if(v==f) continue;
                dfs(v,u);
                siz[u]+=siz[v];
                if(siz[v]>siz[gson[u]]) gson[u]=v;
            }
        }
        void dfs(int u) {
            dfn[u]=eddfn[u]=++cnt;
            idfn[cnt]=u;
            st[0][cnt]=fa[u];
            if(gson[u]) top[gson[u]]=top[u], dfs(gson[u]);
            _max(eddfn[u],eddfn[gson[u]]);
            for(int i=head[u]; i; i=e[i].ne) {
                int v=e[i].to;
                if(v==fa[u] || v==gson[u]) continue;
                top[v]=v, dfs(v);
                _max(eddfn[u],eddfn[v]);
            }
        }
        int tr[N<<2],tag[N<<2];
        int p;
        void build() {
            p=1;
            while(p-2<n) p<<=1;
            rep(i,1,n) tr[p+i]=a[idfn[i]];
            per(i,p-1,1) tr[i]=add(tr[i<<1],tr[i<<1|1]);
        }
        void init() {
            dfs(rt,0);
            // pf("gson "); rep(i,1,n) pf("%d ",gson[i]); pf("\n");
            top[rt]=rt;
            dfs(rt);
            // pf("dfn "); rep(i,1,n) pf("%d ",dfn[i]); pf("\n");
            // pf("eddfn "); rep(i,1,n) pf("%d ",eddfn[i]); pf("\n");
            // pf("top "); rep(i,1,n) pf("%d ",top[i]); pf("\n");
            int lg=__lg(n);
            rep(k,1,lg) for(int i=1;i+(1<<k)-1<=n;i++) st[k][i]=lcamin(st[k-1][i],st[k-1][i+(1<<(k-1))]);
            build();
        }
        void maketag(int u,int x,int siz) { _add(tr[u],1ll*x*siz%p), _add(tag[u],x); }
        void pushup(int u,int siz) { tr[u]=add(add(tr[u<<1],tr[u<<1|1]),1ll*siz*tag[u]); }
        void _update(int l,int r,int x) {
            l=p+l-1, r=p+r+1;
            int siz=1;
            while(l^r^1) {
                if((l&1)^1) maketag(l^1,x,siz);
                if(r&1) maketag(r^1,x,siz);
                l>>=1, r>>=1, siz<<=1;
                pushup(l,siz), pushup(r,siz);
            } 
            for(l>>=1, siz<<=1; l; l>>=1, siz<<=1) pushup(l,siz);
        }
        int _query(int l,int r) {
            l=p+l-1, r=p+r+1;
            int sizl=0,sizr=0,siz=1;
            int s=0;
            while(l^r^1) {
                if((l&1)^1) _add(s,tr[l^1]), sizl+=siz;
                if(r&1) _add(s,tr[r^1]), sizr+=siz;
                l>>=1, r>>=1, siz<<=1;
                _add(s,1ll*tag[l]*sizl%p), _add(s,1ll*tag[r]*sizr%p);
            }
            for(l>>=1, sizl+=sizr; l; l>>=1) _add(s,1ll*tag[l]*sizl%p);
            return s;
        }
        void update(int u,int v,int x) {
            int lca=getlca(u,v);
            // pf("%d %d %d\n",u,v,lca);
            while(dfn[top[u]]>dfn[lca]) _update(dfn[top[u]],dfn[u],x), u=fa[top[u]];
            _update(dfn[lca],dfn[u],x);
            while(dfn[top[v]]>dfn[lca]) _update(dfn[top[v]],dfn[v],x), v=fa[top[v]];
            if(dfn[v]>=dfn[lca]+1) _update(dfn[lca]+1,dfn[v],x);
        }
        void update(int u,int x) {
            _update(dfn[u],eddfn[u],x);
        }
        int query(int u,int v) {
            int lca=getlca(u,v);
            int s=0;
            while(dfn[top[u]]>dfn[lca]) _add(s,_query(dfn[top[u]],dfn[u])), u=fa[top[u]];
            _add(s,_query(dfn[lca],dfn[u]));
            while(dfn[top[v]]>dfn[lca]) _add(s,_query(dfn[top[v]],dfn[v])), v=fa[top[v]];
            if(dfn[v]>=dfn[lca]+1) _add(s,_query(dfn[lca]+1,dfn[v]));
            return s;
        }
        int query(int u) {
            return _query(dfn[u],eddfn[u]);
        }
        // void write() {
            // pf("tr "); rep(i,1,p+n) pf("%d ",tr[i]); pf("\n");
            // pf("tag "); rep(i,1,p+n) pf("%d ",tag[i]); pf("\n");
        // }
    }T;
    int op,x;
    void main() {
        sf("%d%d%d%d",&n,&m,&rt,&p);
        rep(i,1,n) sf("%d",&a[i]), a[i]%=p;
        rep(i,1,n-1) sf("%d%d",&u,&v), addedge(u,v), addedge(v,u);
        T.init();
        // T.write();
        rep(i,1,m) {
            sf("%d",&op);
            if(op==1) sf("%d%d%d",&u,&v,&x), T.update(u,v,x);
            else if(op==2) sf("%d%d",&u,&v), pf("%d\n",T.query(u,v));
            else if(op==3) sf("%d%d",&u,&x), T.update(u,x);
            else sf("%d",&u), pf("%d\n",T.query(u));
            // T.write();
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("my.out","w",stdout);
    #endif
    tree_pou_heavy :: main();
}

by liyixin0514 @ 2024-11-25 22:14:47

楼主不得不回宿舍了，可能今天无法及时回复，见谅。

by SXqwq @ 2024-11-26 15:10:30

好抽象/yun

by L_zaa_L @ 2024-11-26 15:21:51

@liyixin0514兄弟，你那个线段树里的p和模数冲突了

by hepp @ 2024-11-26 15:29:57

@liyixin0514

马蜂差评/fn（

拍出来一组hack,我再看看

5 7 1 13
9 6 3 6 9 
1 2
2 3
1 4
3 5
2 1 5 
4 3 
4 2 
3 1 5 
1 5 4 2 
2 3 4 
2 3 1
ans
1
12
5
0
0

by liyixin0514 @ 2024-11-26 15:32:38

@L_zaa_L 还真是，/bx

by liyixin0514 @ 2024-11-26 15:33:52

不过还是有 bug，变成 46pts 了。

by liyixin0514 @ 2024-11-26 15:34:09

@hepp /bx 我也看看

by L_zaa_L @ 2024-11-26 15:35:45

@liyixin0514 pushup 还忘了取模