WA30pts 树剖求调
  • 板块P3401 洛谷树
  • 楼主114514xxx
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/1 21:37
  • 上次更新2025/7/2 15:26:09
查看原帖
WA30pts 树剖求调
749175
114514xxx楼主2025/7/1 21:37

record

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+25;
struct Edge{
    int to,next,w;
}edge[N];
int head[N],cnt,siz[N],f[N],son[N],g[32];
int dfn[N],rnk[N],top[N],tot,a[N],n,q,dep[N];
int p[N];
struct SGT{
    struct node{
        int l,r,sum,len,tag;
    }t[N];
    #define ls 2*p
    #define rs 2*p+1
    inline void update(int p){
        t[p].sum=t[ls].sum+t[rs].sum;
    }
    inline void spread(int p){
        if(t[p].tag){
            t[ls].sum=t[ls].len-t[ls].sum;
            t[rs].sum=t[rs].len-t[rs].sum;
            t[ls].tag^=1;
            t[rs].tag^=1;
            t[p].tag=0;
        }
    }
    inline void build(int p,int l,int r){
        t[p].l=l,t[p].r=r;
        t[p].len=t[p].r-t[p].l+1;
        if(l==r){return;}
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        update(p);
    }
    inline int query(int p,int l,int r){
        if(t[p].l>=l&&t[p].r<=r)return t[p].sum;
        int mid=(t[p].l+t[p].r)>>1;
        spread(p);
        int ans=0;
        if(l<=mid)ans+=query(ls,l,r);
        if(r>mid)ans+=query(rs,l,r);
        update(p);
        return ans;
    }
    inline void modify(int p,int l,int r){
        if(t[p].l>=l&&t[p].r<=r){
            t[p].sum=t[p].len-t[p].sum;
            t[p].tag^=1;
            return;
        }
        spread(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(l<=mid)modify(ls,l,r);
        if(r>mid)modify(rs,l,r);
        update(p);
    }
    inline void change(int p,int x,int k){
        if(t[p].l==t[p].r&&t[p].l==x){
            t[p].sum=k;
            return;
        }
        int mid=(t[p].l+t[p].r)>>1;
        spread(p);
        if(x<=mid)change(ls,x,k);
        if(x>mid)change(rs,x,k);
        update(p);
        return;
    }
}t[15];
inline void add(int x,int y,int z){
    edge[++cnt].to=y;
    edge[cnt].next=head[x];
    edge[cnt].w=z;
    head[x]=cnt;
}
inline void dfs1(int u,int fa){
    f[u]=fa;
    dep[u]=dep[fa]+1;
    siz[u]=1;son[u]=-1;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(son[u]==-1||siz[son[u]]<=siz[v])son[u]=v;
    }
}
inline void dfs2(int u,int topf){
    top[u]=topf;
    ++tot;dfn[u]=tot;rnk[dfn[u]]=u;
    if(son[u]==-1)return;
    dfs2(son[u],topf);
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==f[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
inline void binary(int x){
    int cnt=0;
    for(int i=0;i<=15;i++)g[i]=0;
    while(x){
        g[cnt]=x&1;
        ++cnt,x>>=1;
    }
}
inline void init(int u,int fa){
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa)continue;
        a[v]=a[u]^edge[i].w;
        init(v,u);
    }
}
inline int pquery(int k,int x,int y){
    int ans=0;
    if(dep[x]<dep[y])swap(x,y);
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans+=t[k].query(1,dfn[top[x]],dfn[x]);
        x=f[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    ans+=t[k].query(1,dfn[y],dfn[x]);
    return ans;
}
inline void pmodify(int x,int k){
    int cnt=0;int w=a[x];
    for(int i=0;i<=15;i++)p[i]=0;
    while(w){
        p[cnt]=w&1;
        ++cnt,w>>=1;
    }
    a[x]=k;
    binary(k);
    for(int i=0;i<=10;i++)
        if(g[i]!=p[i])t[i].modify(1,dfn[x],dfn[x]+siz[x]-1);
}
int lca(int u,int v) {
    if(dep[u]<dep[v])swap(u,v);
    while(top[u]!=top[v])
        if(dep[top[u]]>dep[top[v]])
            u=f[top[u]];
        else
            v=f[top[v]];
    return dep[u]>dep[v]?v:u;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    int u,v,w;
    for(int i=1;i<n;i++){
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    init(1,0);
    dfs1(1,0);
    dfs2(1,1);
    for(int i=0;i<=10;i++)
        t[i].build(1,1,n);
    for(int i=1;i<=n;i++){
        binary(a[i]);
        for(int j=0;j<=10;j++)
            t[j].change(1,dfn[i],g[j]);
    }
    int opt;
    while(q--){
        cin>>opt;
        if(opt==1){
            cin>>u>>v;
            int ans=0;
            int p3=dep[u]+dep[v]-2*dep[lca(u,v)]+1;
            for(int i=0;i<=10;i++){
                int p1=(1<<i),p2=0;
                p2=pquery(i,u,v);
                ans+=p1*p2*(p3-p2);
            }
            cout<<ans<<'\n';
        }else{
            cin>>u>>v>>w;
            if(dep[u]<dep[v])swap(u,v);
            pmodify(u,w);
        }
    }
}

2025/7/1 21:37
加载中...