(Luogu) P3950 部落冲突 (LCT || 树链剖分)

本文主要是介绍(Luogu) P3950 部落冲突 (LCT || 树链剖分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

解：LCT解决这个就非常直接了，直接断边连边，检查一下连通性就行了。

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
#define ls ch[x][0]
#define rs ch[x][1]
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=3e5+5;
template <typename _Tp> il void read(_Tp&x) {char ch;bool flag=0;x=0;while(ch=getchar(),!isdigit(ch)) if(ch=='-')flag=1;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();if(flag) x=-x;
}
//il int Add(int &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(int &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int f[N],ch[N][2],v[N],s[N],st[N],sz[N];
bool r[N];
il bool isroot(int x){return ch[f[x]][0]==x || ch[f[x]][1]==x; 
} 
il void pushup(int x){sz[x]=sz[ls]+sz[rs]+1; 
}
il void reverse(int x){swap(ls,rs),r[x]^=1;
}
il void pushdown(int x){if(r[x]){if(ls) reverse(ls);if(rs) reverse(rs);r[x]=0;}
}
il void rotate(int x){int y=f[x],z=f[y],k=(ch[y][1]==x),w=ch[x][!k];if(isroot(y))	ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=w;if(w) f[w]=y;f[y]=x,f[x]=z;pushup(y);
}
il void splay(int x){int y=x,z=0;st[++z]=y;while(isroot(y)) st[++z]=y=f[y];while(z) pushdown(st[z--]);while(isroot(x)){y=f[x],z=f[y];if(isroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);rotate(x);}pushup(x);
}il void access(int x){for(int y=0;x;x=f[y=x]){splay(x),rs=y,pushup(x);}
}
il void makeroot(int x){access(x),splay(x);reverse(x);
}
il int findroot(int x){//查找在原树的根 access(x),splay(x);while(ls) pushdown(x),x=ls;splay(x);return x;
}
il void split(int x,int y){makeroot(x);access(y),splay(y);
}
//保证合法的情况下 
il void link(int x,int y){makeroot(x),f[x]=y;
}
il void cut(int x,int y){split(x,y);f[x]=ch[y][0]=0;
}int n,m;
char op[2];
struct node{int u,v;
}q[N];
int main() {read(n),read(m);int x,y,cnt=0;for(int i=1;i<=n-1;++i){read(x),read(y);link(x,y);}while(m--){scanf("%s",op);if(op[0]=='Q'){read(x),read(y);if(findroot(x)==findroot(y)) printf("Yes\n");else printf("No\n");}else if(op[0]=='C'){read(x),read(y);q[++cnt]={x,y};cut(x,y);}else{read(x);link(q[x].u,q[x].v);}}return 0;
}

解：当边上有战争时，那就将这条边+1，查询x能否到y，就是查询x到y的路径权值和是否为0，树剖本来维护点，我们将每条边分给边上深度较大的一个点上，无论是修改还是查询操作，先全部算上，然后只要对x，y的最近公共祖先取消他的操作就可以了。

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=3e5+5; 
template <typename _Tp> il void read(_Tp&x) {char ch;bool flag=0;x=0;while(ch=getchar(),!isdigit(ch)) if(ch=='-')flag=1;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();if(flag) x=-x;
}
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
vector<int> G[N]; 
int n,m,dep[N],sz[N],son[N],fa[N],id[N],bel[N],cnt;
il void dfs1(int x,int ff){fa[x]=ff,dep[x]=dep[ff]+1,sz[x]=1;int mx=-1;for(auto to:G[x]){if(to==ff) continue;dfs1(to,x);sz[x]+=sz[to];if(sz[to]>mx) son[x]=to,mx=sz[to];}
} 
il void dfs2(int x,int topx){id[x]=++cnt,bel[x]=topx;if(!son[x]) return ;dfs2(son[x],topx);for(auto to:G[x]){if(to==fa[x] || to==son[x]) continue;dfs2(to,to);} 
}
int lz[N<<2],s[N<<2],tsz[N<<2];
il void pushdown(int rt){if(lz[rt]){lz[rt<<1]+=lz[rt],lz[rt<<1|1]+=lz[rt];s[rt<<1]+=tsz[rt<<1]*lz[rt];s[rt<<1|1]+=tsz[rt<<1|1]*lz[rt];lz[rt]=0;}
} 
il void build(int l,int r,int rt){if(l==r){tsz[rt]=1;return;}build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);tsz[rt]=tsz[rt<<1]+tsz[rt<<1|1];
}
il void update(int l,int r,int rt,int L,int R,int C){if(L<=l && r<=R){s[rt]+=C*tsz[rt],lz[rt]+=C;return;}pushdown(rt);if(L<=mid) update(l,mid,rt<<1,L,R,C);if(R>mid) update(mid+1,r,rt<<1|1,L,R,C);s[rt]=s[rt<<1]+s[rt<<1|1];
}
il int query(int l,int r,int rt,int L,int R){if(L<=l && r<=R){return s[rt];}int ans=0;pushdown(rt);if(L<=mid) ans+=query(l,mid,rt<<1,L,R);if(R>mid) ans+=query(mid+1,r,rt<<1|1,L,R);return ans;
} 
il void r_update(int x,int y,int w){while(bel[x]!=bel[y]){if(dep[bel[x]]<dep[bel[y]]) swap(x,y);update(1,n,1,id[bel[x]],id[x],w);x=fa[bel[x]];}if(dep[x]>dep[y]) swap(x,y);update(1,n,1,id[x],id[y],w);update(1,n,1,id[x],id[x],-w);
}
il int r_ask(int x,int y){int res=0;while(bel[x]!=bel[y]){if(dep[bel[x]]<dep[bel[y]]) swap(x,y);res+=query(1,n,1,id[bel[x]],id[x]);x=fa[bel[x]];}if(dep[x]>dep[y]) swap(x,y);res+=query(1,n,1,id[x],id[y]);res-=query(1,n,1,id[x],id[x]);return res;
}
char op[2];
struct node{int u,v;
}q[N];
int main(){read(n),read(m);int x,y,tot=0;for(int i=1;i<=n-1;++i){read(x),read(y);G[x].pb(y),G[y].pb(x);}dfs1(1,0);dfs2(1,1);build(1,n,1);while(m--){scanf("%s",op);if(op[0]=='Q'){read(x),read(y);if(r_ask(x,y)==0) printf("Yes\n");else printf("No\n");}else if(op[0]=='C'){read(x),read(y);q[++tot]={x,y};r_update(x,y,1);}else{read(x);r_update(q[x].u,q[x].v,-1);}}return 0;
}

 

这篇关于(Luogu) P3950 部落冲突 (LCT || 树链剖分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---