只是一些炸掉的树剖罢了 洛谷10pts 样例没过qwq

常规
1 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
#define int long long

ll idx,nxt[N],to[N],w[N],wt[N],hd[N],res,depth[N],siz[N],top[N],son[N],id[N],fa[N];
ll n,m,r,Q,ns[N],tree[N<<2],tag[N<<2],cnt;
void add(ll x,ll y){
    to[++idx] = y;
    nxt[idx] = hd[x];
    hd[x] = idx;
}
//-------------------- Segment Tree
ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
void push_up(ll rt){
    tree[rt] = (tree[ls(rt)] + tree[rs(rt)])%Q;
}
void build(ll rt,ll l,ll r){
    if(l == r){
        tree[rt] = ns[l];
        tree[rt] %= Q;
        return;
    }
    ll mid = (l+r)>>1;
    build(ls(rt),l,mid); build(rs(rt),mid+1,r);
    push_up(rt);
}
void f(ll rt,ll l,ll r,ll k){
    tag[rt] += k;
    tree[rt] += k*(r-l+1);
    tag[rt] %= Q; tree[rt] %= Q;
}
void push_down(ll rt,ll l,ll r){
    ll mid = (l+r)>>1;
    f(ls(rt),l,mid,tag[rt]);
    f(rs(rt),mid+1,r,tag[rt]);
    tag[rt] = 0;
}
void update(ll nl,ll nr,ll rt,ll l,ll r,ll k){
    if(nl <= l && r <= nr){
        tree[rt] += k*(r-l+1);
        tag[rt] += k;
        tree[rt] %= Q;
        tag[rt] %= Q;
        return;
    }
    push_down(rt,l,r);
    ll mid = (l+r)>>1;
    if(nl<=mid) update(nl,nr,ls(rt),l,mid,k);
    if(nr>mid) update(nl,nr,rs(rt),mid+1,r,k);
    push_up(rt);
}
void query(ll nl,ll nr,ll rt,ll l,ll r){
    ll ans = 0;
    if(nl<=l && r<=nr){
        res += tree[rt]; res %= Q;
        if(tree[rt] >Q) tree[rt] %= Q;
        return;
    }
    ll mid = (l+r)>>1;
    if(tag[rt]) push_down(rt,l,r);
    if(nl <= mid) query(nl,nr,ls(rt),l,mid);
    if(nr > mid) query(nl,nr,rs(rt),mid+1,r);
}
//----------------------树剖↓
void dfs1(int x,int f,int dep){
    depth[x] = dep; fa[x] = f; siz[x] = 1;
    int max_son = -1;
    for(int i=hd[x];i;i = nxt[i]){
        int v = to[i];
        if(v != f){
            dfs1(v,x,dep+1);
            siz[x] += siz[v];
            if(siz[v] > max_son) son[x] = v,max_son = siz[v];
        }
    }
}

void dfs2(int x,int topp){
    id[x] = ++cnt; wt[cnt] = w[x]; //new node
    top[x] = topp;
    if(!son[x]) return;
    dfs2(son[x],topp); //继续链
    for(int i=hd[x];i;i = nxt[i]){
        int v = to[i];
        if(v == fa[x] || v == son[x]) continue; //在同一条链上
        dfs2(v,v); //new
    }
}
// -------------------这道题
inline int qRange(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){//当两个点不在同一条链上 
        if(depth[top[x]]<depth[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
        res=0;
        query(id[top[x]],id[x],1,1,n);//ans加上x点到x所在链顶端 这一段区间的点权和
        ans+=res;
        ans%=Q;//按题意取模 
        x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
    }
    //直到两个点处于一条链上
    if(depth[x]>depth[y])swap(x,y);//把x点深度更深的那个点
    res=0;
    query(id[x],id[y],1,1,n);//这时再加上此时两个点的区间和即可
    ans+=res;
    return ans%Q;
}

void upRange(int x,int y,int k){
    k%=Q;
    while(top[x] != top[y]){
        if(depth[top[x]] < depth[top[y]]) swap(x,y);
        update(id[top[x]],id[x],1,1,n,k);
        x = fa[top[x]];
    }
    if(depth[x] > depth[y]) swap(x,y);
    update(id[x],id[y],1,1,n,k);
}

int qSon(int x){
    res = 0;
    query(id[x],id[x] + siz[x] - 1,1,1,n);
    return res;
}

void updSon(int x,int k){
    update(id[x],id[x]+siz[x]-1,1,1,n,k);
}

signed main(){
    scanf("%lld %lld %lld %lld",&n,&m,&r,&Q);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(int i=1;i<=n-1;i++){
        int l,r; scanf("%lld %lld",&l,&r);
        add(l,r); add(r,l);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    for(;m--;){
        int typ,x,y,z;
        scanf("%lld",&typ);
        if(typ == 1){
            scanf("%lld %lld %lld",&x,&y,&z);
            upRange(x,y,z);
        }
        else if(typ == 2){
            scanf("%lld %lld",&x,&y);
            printf("%lld\n",qRange(x,y));
        }
        else if(typ == 3){
            scanf("%lld %lld",&x,&y);
            updSon(x,y);
        }
        else{
            scanf("%lld",&x);
            printf("%lld\n",qSon(x));
        }
    }

    return 0;
}

树剖板子

这个鬼东西跑不过样例，但是放到洛谷上居然有10分……
有可能是我线段树炸了，如果真的想帮我调不要忽略它（）
说起来也是奇怪，我树剖题都做了好几道了板子过不去
、、、、、

1 个赞