题解 SP16549 【QTREE6 - Query on a tree VI】
xukuan
2020-01-19 09:13:20
操作有两种,一种是问相同颜色的点的大小,一种是改变点的颜色。
众所周知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;
}
```