树剖求调

white_carton @ 2023-06-21 21:04:54

#include<bits/stdc++.h>
#define int long long
#define soon a[i].to
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int cnt,n,m,r,mod,head[1000100],top[1001000],fa[1001000];
int son[1001000],siz[1001000],dfn[1001000],dep[1001000],sum,x[1001000];
int dc=0;
struct xdt{
    #define ls p<<1
    #define rs p<<1|1
    int d[1001000],b[1001000],a[1000100];
    void pushup(int p){
        d[p]=d[ls]+d[rs];
        d[p]=d[p]%mod;
    }
    void build(int s,int t,int p){
        if(s==t){
            d[p]=a[s]%mod;
            return;
        }
        int m=(s+t)>>1;
        build(s,m,ls);
        build(m+1,t,rs);
        pushup(p);
    }
    void update(int l,int r,int c,int s,int t,int p){
    //  cout<<l<<" "<<r<<" "<<c<<" "<<s<<" "<<t<<" "<<p<<endl;
        if(l<=s&&t<=r){
            d[p]+=(t-s+1)*c%mod;
            b[p]+=c%mod;
//          cout<<1<<endl;
            return;
        }
        int m=(t+s)>>1;
        if(b[p]&&s!=t){
            d[ls]+=b[p]*(m-s+1)%mod;
            d[rs]+=b[p]*(t-m)%mod;
            b[ls]+=b[p]%mod;
            b[rs]+=b[p]%mod;
            b[p]=0;
        }
        cout<<1<<endl;
        if(l<=m){
        //  printf("%lld %lld %lld %lld %lld %lld\n",l,r,c,s,m,ls);
            update(l,r,c,s,m,ls);
        }
        if(m<r){
        //  printf("%lld %lld %lld %lld %lld %lld\n",l,r,c,m+1,t,rs);
            update(l,r,c,m+1,t,rs);
        }
        pushup(p);
    }
    int getsum(int l,int r,int s,int t,int p){
        if(l<=s&&t<=r){
            return d[p]%mod;
        }
        int m=(s+t)>>1;
        if(b[p]){
            d[ls]+=b[p]*(m-s+1)%mod;
            d[rs]+=b[p]*(t-m)%mod;
            b[ls]+=b[p]%mod;
            b[rs]+=b[p]%mod;
            b[p]=0;
        }
        int sum=0;
        if(l<=m){
            sum=getsum(l,r,s,m,ls)%mod;
        }
        if(r>m){
            sum+=getsum(l,r,m+1,t,rs)%mod;
        }
        return sum;
    }
}tree;
struct node{
    int nxt,to;
}a[1000100];
int add(int u,int v){
    a[++cnt].nxt=head[u];
    a[cnt].to=v;
    head[u]=cnt;
}
void dfs1(int p,int f){
    fa[p]=f;
    son[p]=-1;
    siz[p]=1;
    for(int i=head[p];i;i=a[i].nxt){
        if(soon!=f){
            dep[soon]=dep[p]+1;
        //  fa[soon]=p;
            dfs1(soon,p);
            siz[p]+=siz[soon];
            if(son[p]==-1||siz[soon]>siz[son[p]]){
                son[p]=soon;
            }
        }
    }
}
void dfs2(int p,int t){
    top[p]=t;
    dfn[p]=++sum;
    tree.a[sum]=x[p];
    //rnk[sum]=p;
    if(son[p]==-1){
        return;
    }
    dfs2(son[p],t);
    for(int i=head[p];i;i=a[i].nxt){
        if(soon!=son[p]&&soon!=fa[p]){
            dfs2(soon,soon);
        }
    }
}
int treesum(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
//      cout<<x<<" "<<y<<endl;
        if(dep[top[x]]<dep[top[y]]){
            swap(x,y);
        }
        //cout<<x<<" "<<y<<endl;
        ans=(ans+tree.getsum(dfn[top[x]],dfn[x],1,n,1))%mod;
        x=fa[top[x]];
        //cout<<x<<" "<<top[x]<<" "<<fa[top[x]]<<endl;
    }
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    return ans=(ans+tree.getsum(dfn[x],dfn[y],1,n,1))%mod;
}
int treeadd(int x,int y,int v){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]){
            swap(x,y);
        }
        tree.update(dfn[top[x]],dfn[x],v%mod,1,n,1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    tree.update(dfn[x],dfn[y],v%mod,1,n,1);
}
void solve(){
    cin>>n>>m>>r>>mod;
    for(int i=1;i<=n;i++){
        cin>>x[i];
    }
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs1(r,0),dfs2(r,r);
    tree.build(1,n,1);
//  cout<<son[1]<<endl;
    for(int i=1,op,x,y,z;i<=m;i++){
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            treeadd(x,y,z);
        }
        if(op==2){
            cin>>x>>y;
            cout<<treesum(x,y)<<endl;
        }
        if(op==3){
            cin>>x>>y;
            //cout<<dfn[x]<<" "<<siz[x]<<endl;
            tree.update(dfn[x],dfn[x]+siz[x]-1,y%mod,1,n,1);
        }
        if(op==4){
            cin>>x;
            cout<<tree.getsum(dfn[x],dfn[x]+siz[x]-1,1,n,1)<<endl;
        }
    }
}
signed main(){
    int t=(dc?read():1);
    while(t--)
        solve();
    return 0;
} 

by white_carton @ 2023-06-21 21:08:38

悬1关

by eggegg185 @ 2023-06-22 11:12:45

@starback24 你活珠子大跌来给你调题了！（bushi 就是bzd为什么有个蜜汁缩进（不好意思

            #include<iostream>
            #define int long long
            #define soon a[i].to
            using namespace std;
            inline int read(){
                int x=0,f=1;
                char ch=getchar();
                while(ch<'0'||ch>'9'){
                    if(ch=='-')
                        f=-1;
                    ch=getchar();
                }
                while(ch>='0'&&ch<='9'){
                    x=(x<<1)+(x<<3)+(ch^48);
                    ch=getchar();
                }
                return x*f;
            }
            int cnt,n,m,r,mod,head[1000100],top[1001000],fa[1001000];
            int son[1001000],siz[1001000],dfn[1001000],dep[1001000],sum,x[1001000];
            int dc=0;
            struct xdt{
                #define ls p<<1
                #define rs p<<1|1
                int d[1001000],b[1001000],a[1000100];
                void pushup(int p){
                    d[p]=d[ls]+d[rs];
                    d[p]=d[p]%mod;
                }
                void build(int s,int t,int p){
                    if(s==t){
                        d[p]=a[s]%mod;
                        return;
                    }
                    int m=(s+t)>>1;
                    build(s,m,ls);
                    build(m+1,t,rs);
                    pushup(p);
                }
                void update(int l,int r,int c,int s,int t,int p){
                    //  cout<<l<<" "<<r<<" "<<c<<" "<<s<<" "<<t<<" "<<p<<endl;
                    if(l<=s&&t<=r){
                        d[p]+=(t-s+1)*c%mod;
                        b[p]+=c%mod;
                        //          cout<<1<<endl;
                        return;
                    }
                    int m=(t+s)>>1;
                    if(b[p]&&s!=t){
                        d[ls]+=b[p]*(m-s+1)%mod;
                        d[rs]+=b[p]*(t-m)%mod;
                        b[ls]+=b[p]%mod;
                        b[rs]+=b[p]%mod;
                        b[p]=0;
                    }
                    //cout<<1<<endl;
                    if(l<=m){
                        //  printf("%lld %lld %lld %lld %lld %lld\n",l,r,c,s,m,ls);
                        update(l,r,c,s,m,ls);
                    }
                    if(m<r){
                        //  printf("%lld %lld %lld %lld %lld %lld\n",l,r,c,m+1,t,rs);
                        update(l,r,c,m+1,t,rs);
                    }
                    pushup(p);
                }
                int getsum(int l,int r,int s,int t,int p){
                    if(l<=s&&t<=r){
                        return d[p]%mod;
                    }
                    int m=(s+t)>>1;
                    if(b[p]){
                        d[ls]+=b[p]*(m-s+1)%mod;
                        d[rs]+=b[p]*(t-m)%mod;
                        b[ls]+=b[p]%mod;
                        b[rs]+=b[p]%mod;
                        b[p]=0;
                    }
                    int sum=0;
                    if(l<=m){
                        sum=getsum(l,r,s,m,ls)%mod;
                    }
                    if(r>m){
                        sum+=getsum(l,r,m+1,t,rs)%mod;
                    }
                    return sum;
                }
            }tree;
            struct node{
                int nxt,to;
            }a[1000100];
            void add(int u,int v){
                a[++cnt].nxt=head[u];
                a[cnt].to=v;
                head[u]=cnt;
            }
            void dfs1(int p,int f){
                fa[p]=f;
                son[p]=-1;
                siz[p]=1;
                for(int i=head[p];i;i=a[i].nxt){
                    if(soon!=f){
                        dep[soon]=dep[p]+1;
                        //  fa[soon]=p;
                        dfs1(soon,p);
                        siz[p]+=siz[soon];
                        if(son[p]==-1||siz[soon]>siz[son[p]]){
                            son[p]=soon;
                        }
                    }
                }
            }
            void dfs2(int p,int t){
                top[p]=t;
                dfn[p]=++sum;
                tree.a[sum]=x[p];
                //rnk[sum]=p;
                if(son[p]==-1){
                    return;
                }
                dfs2(son[p],t);
                for(int i=head[p];i;i=a[i].nxt){
                    if(soon!=son[p]&&soon!=fa[p]){
                        dfs2(soon,soon);
                    }
                }
            }
            int treesum(int x,int y){
                int ans=0;
                while(top[x]!=top[y]){
                    //      cout<<x<<" "<<y<<endl;
                    if(dep[top[x]]<dep[top[y]]){
                        swap(x,y);
                    }
                    //cout<<x<<" "<<y<<endl;
                    ans=(ans+tree.getsum(dfn[top[x]],dfn[x],1,n,1))%mod;
                    x=fa[top[x]];
                    //cout<<x<<" "<<top[x]<<" "<<fa[top[x]]<<endl;
                }
                if(dep[x]>dep[y]){
                    swap(x,y);
                }
                return ans=(ans+tree.getsum(dfn[x],dfn[y],1,n,1))%mod;
            }
            void treeadd(int x,int y,int v){
                while(top[x]!=top[y]){
                    if(dep[top[x]]<dep[top[y]]){
                        swap(x,y);
                    }
                    tree.update(dfn[top[x]],dfn[x],v%mod,1,n,1);
                    x=fa[top[x]];
                }
                if(dep[x]>dep[y]){
                    swap(x,y);
                }
                tree.update(dfn[x],dfn[y],v%mod,1,n,1);
            }
            void solve(){
                cin>>n>>m>>r>>mod;
                for(int i=1;i<=n;i++){
                    cin>>x[i];
                }
                for(int i=1,x,y;i<n;i++){
                    cin>>x>>y;
                    add(x,y);
                    add(y,x);
                }
                dfs1(r,0),dfs2(r,r);
                tree.build(1,n,1);
                //  cout<<son[1]<<endl;
                for(int i=1,op,x,y,z;i<=m;i++){
                    cin>>op;
                    if(op==1){
                        cin>>x>>y>>z;
                        treeadd(x,y,z);
                    }
                    if(op==2){
                        cin>>x>>y;
                        cout<<treesum(x,y)%mod<<endl;
                    }
                    if(op==3){
                        cin>>x>>y;
                        //cout<<dfn[x]<<" "<<siz[x]<<endl;
                        tree.update(dfn[x],dfn[x]+siz[x]-1,y%mod,1,n,1);
                    }
                    if(op==4){
                        cin>>x;
                        cout<<tree.getsum(dfn[x],dfn[x]+siz[x]-1,1,n,1)%mod<<endl;
                    }
                }
            }
            signed main(){
                int t=(dc?read():1);
                while(t--)
                    solve();
                return 0;
            } 

by white_carton @ 2023-06-22 11:25:10

@eggegg185 谢谢龟孙

by white_carton @ 2023-06-22 11:25:25

@eggegg185 没有关给你了

by eggegg185 @ 2023-06-22 11:29:09

@starback24 好好好