题解 SP16549 【QTREE6 - Query on a tree VI】

xukuan

2020-01-19 09:13:20

Solution

操作有两种,一种是问相同颜色的点的大小,一种是改变点的颜色。 众所周知Qtree系列是LCT的题目,那么这题怎么用LCT去解决? 相对于传统的维护区间的LCT,我们还要再开一个sum来维护子树的大小。 开两颗lct,询问的时候直接输出根节点右儿子的sum,翻转就是先再一颗lct里把它删掉再再另一颗lct里加上去 代码: ```cpp #include<bits/stdc++.h> #include<iostream> #include<cstdio> #define ll long long using namespace std; const ll N=100010; ll n,m,fa[N],colour[N]; ll ver[N<<1],Next[N<<1],head[N],tot; inline ll read(){ ll x=0,tmp=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') tmp=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return tmp*x; } inline void write(ll x){ if(x<0){ putchar('-'); x=-x; } ll y=10,len=1; while(y<=x){ y=(y<<3)+(y<<1); len++; } while(len--){ y/=10; putchar(x/y+48); x%=y; } } inline void addEdge(ll x,ll y){ ver[++tot]=y; Next[tot]=head[x]; head[x]=tot; } struct LCT{ struct Link_Cut_tree{ ll son[2],father,sum,size; }tree[N]; LCT(){for(ll i=1; i<N; i++) tree[i].sum=1;} inline void pushup(ll p){ tree[p].sum=tree[tree[p].son[0]].sum+tree[tree[p].son[1]].sum+tree[p].size+1; } inline bool isroot(ll p){ return tree[tree[p].father].son[0]!=p&&tree[tree[p].father].son[1]!=p; } inline bool which(ll p){ return tree[tree[p].father].son[1]==p; } inline void rotate(ll p){ ll fa=tree[p].father,fafa=tree[fa].father; bool w=which(p); if(!isroot(fa)) tree[fafa].son[which(fa)]=p; tree[fa].son[w]=tree[p].son[w^1]; tree[tree[p].son[w^1]].father=fa; tree[p].son[w^1]=fa; tree[fa].father=p; tree[p].father=fafa; pushup(fa); pushup(p); } inline void splay(ll p){ for(ll i=tree[p].father; !isroot(p); rotate(p),i=tree[p].father){ if(!isroot(i)){ if(which(i)==which(p)) rotate(i); else rotate(p); } } pushup(p); } inline void access(ll p){ for(ll y=0; p; p=tree[y=p].father){ splay(p); tree[p].size+=tree[tree[p].son[1]].sum; tree[p].size-=tree[tree[p].son[1]=y].sum; pushup(p); } } inline ll getroot(ll p){ access(p); splay(p); while(tree[p].son[0]) p=tree[p].son[0]; splay(p); return p; } inline void makeroot(ll p){ access(p); splay(p); } inline void split(ll x,ll y){ makeroot(x); access(y); splay(y); } inline void link(ll p){ access(p); splay(p); ll y=tree[p].father=fa[p]; access(y); splay(y); tree[y].size+=tree[p].sum; tree[y].sum+=tree[p].sum; } inline void cut(ll p){ access(p); splay(p); tree[p].son[0]=tree[tree[p].son[0]].father=0; pushup(p); } }lct[2]; void dfs(ll x){ for(ll i=head[x]; i; i=Next[i]){ ll y=ver[i]; if(y==fa[x]) continue; fa[y]=x; dfs(y); lct[0].link(y); } } int main(){ n=read(); for(ll i=1; i<n; i++){ ll x=read(),y=read(); addEdge(x,y); addEdge(y,x); } dfs(1); fa[1]=n+1; lct[0].link(1); m=read(); while(m--){ ll op=read(),x=read(); switch(op){ case 0:{ ll y=lct[colour[x]].getroot(x); write(lct[colour[x]].tree[lct[colour[x]].tree[y].son[1]].sum); putchar('\n'); break; } case 1:{ lct[colour[x]].cut(x); colour[x]^=1; lct[colour[x]].link(x); break; } } } return 0; } ```