题目传送门
部落冲突
格式难调, 体面就不放了.
分析:
julao 们应该都看得出来就是个 $LCT$ 板子, 战争就 $cut$, 结束就 $link$, 询问就 $find$. 没了...
太久没打 $LCT$, 然后发现自己之前貌似理解得并不透彻, 打得还是不熟...
- Code:
- //It is made by HolseLee on 5th Sep 2018
- //Luogu.org P3950
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<cmath>
- #include<iostream>
- #include<iomanip>
- #include<algorithm>
- using namespace std;
- const int N=3e5+7;
- int n,m,fa[N],ch[N][2],sign[N],cnt,q[N],top;
- struct War{
- int x,y; bool flag;
- }a[N];
- inline int read()
- {
- char c=getchar(); int num=0; bool flag=false;
- while( c<'0' || c>'9' ) {
- if( c=='-' ) flag=false;
- c=getchar();
- }
- while( c>='0' && c<='9' ) {
- num=(num<<1)+(num<<3)+(c^48);
- c=getchar();
- }
- return flag ? -num : num;
- }
- inline void pushdown(int x)
- {
- if( !sign[x] ) return;
- int temp=ch[x][0];
- sign[ch[x][0]=ch[x][1]]^=1;
- sign[ch[x][1]=temp]^=1;
- sign[x]=0;
- }
- inline bool isroot(int x)
- {
- return (ch[fa[x]][0]!=x && ch[fa[x]][1]!=x);
- }
- inline void rotate(int x)
- {
- int y=fa[x], z=fa[y];
- int k=ch[y][1]==x, w=ch[x][k^1];
- if( !isroot(y) ) ch[z][ch[z][1]==y]=x;
- ch[x][k^1]=y; ch[y][k]=w;
- if( w ) fa[w]=y; fa[x]=z; fa[y]=x;
- }
- inline void splay(int x)
- {
- top=1; q[top]=x;
- for(int i=x; !isroot(i); i=fa[i])
- q[++top]=fa[i];
- while( top ) pushdown(q[top--]);
- while( !isroot(x) ) {
- int y=fa[x], z=fa[y];
- if( !isroot(y) ) {
- (ch[y][1]==x)^(ch[z][1]==y) ? rotate(x) : rotate(y);
- }
- rotate(x);
- }
- }
- inline void access(int x)
- {
- for(int y=0; x; y=x,x=fa[x]) {
- splay(x); ch[x][1]=y;
- }
- }
- inline int find(int x)
- {
- access(x); splay(x);
- while( ch[x][0] )pushdown(x),x=ch[x][0];
- splay(x);
- return x;
- }
- inline void makeroot(int x)
- {
- access(x); splay(x); sign[x]^=1;
- }
- inline void split(int x,int y)
- {
- makeroot(x); access(y); splay(y);
- }
- inline void link(int x,int y)
- {
- makeroot(x);
- fa[x]=y;
- }
- inline void cut(int x,int y)
- {
- split(x,y);
- fa[x]=ch[y][0]=0;
- }
- int main()
- {
- n=read(); m=read();
- char opt[2]; int x,y;
- for(int i=1; i<n; ++i) {
- x=read(), y=read();
- link(x,y);
- }
- for(int i=1; i<=m; ++i) {
- scanf("%s",opt);
- if( opt[0]=='Q' ) {
- x=read(), y=read();
- if( find(y)==find(x) ) printf("Yes\n");
- else printf("No\n");
- } else if( opt[0]=='C' ) {
- x=read(), y=read();
- cut(x,y);
- a[++cnt].x=x, a[cnt].y=y;
- a[cnt].flag=false;
- } else {
- x=read();
- if( a[x].flag ) continue;
- link(a[x].x,a[x].y);
- a[x].flag=true;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2756566.html