洛谷SP16549 QTREE6 - Query on a tree VI（LCT)

洛谷題目傳送門

思路分析

題意就是要維護同色連通塊大小。要用LCT維護子樹大小就不說了，可以看看蒟蒻的LCT總結。

至于連通塊如何維護，首先肯定可以想到一個很naive的做法：直接維護同色連通塊，每次更改時暴力修改父邊和子邊。。。。。。

來個菊花圖吧！（話說我真的好弱，前幾天ZJOI的時候才知道對于某點度數很大的樹/圖有這樣的稱呼，真是很形象哈23333）

既然這條路行不通，那就換一種模型吧。

這是一種進階的維護染色連通塊的較為通用的模型。

感覺蒟蒻對這種模型的了解與許多巨佬有不一樣的地方，在這兒瞎扯扯吧

很多與樹有關的題目，當邊權不好處理時，有時候會轉化為此邊子節點的點權處理。

因為有根樹中除了根，每個點都有唯一的父邊。

在這一題裡，道理是一樣的，但轉化方向卻是反的，要把點化為邊！

把每個點的父邊賦予該點的顔色。我們需要兩個LCT，每種對應一個顔色。一條邊隻有在對應顔色的LCT中才會被連上。

于是，原來同色點的連通塊，就變成了剪開頂端節點後的邊的連通塊（解釋一下，因為點的顔色給了父邊，那麼既然是頂端節點，那它的父邊就不會在連通塊中，也就是這個點與連通塊不同色，于是該點的所有子樹不能連起來，于是要剪掉）

然後就可以驚訝地發現，修改一個點的顔色之後，隻要在原來顔色對應LCT中斷掉父邊，再在新顔色對應LCT中連接配接父邊，就可以輕而易舉地維護連通塊啦。

再談查詢，上面提到了要剪開頂端節點（也就是連通塊構成的樹的樹根），于是先findroot，再輸出它的重子樹的大小。

一個小細節，1節點是沒有父親的，不過為了模型的建立，要有父邊，于是需要加一個虛點，讓1的父親指向它連邊。

#include<cstdio>
#include<cstdlib>
#define R register int
#define I inline void
const int N=1000009,M=N<<1;
#define lc c[x][0]
#define rc c[x][1]
#define C col[u]
int fa[N],he[N],ne[M],to[M];
bool col[N];
struct LCT{
	int f[N],c[N][2],si[N],s[N],h[N];
	bool r[N];
	LCT(){for(R i=1;i<N;++i)s[i]=1;}//注意初始化
	inline bool nroot(R x){return c[f[x]][0]==x||c[f[x]][1]==x;}
	I pushup(R x){
		s[x]=s[lc]+s[rc]+si[x]+1;
	}
	I rotate(R x){
		R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
		if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
		f[w]=y;f[y]=x;f[x]=z;
		pushup(y);
	}
	I splay(R x){
		R y;
		while(nroot(x)){
			if(nroot(y=f[x]))rotate((c[f[y]][0]==y)^(c[y][0]==x)?x:y);
			rotate(x);
		}
		pushup(x);
	}
	I access(R x){
		for(R y=0;x;x=f[y=x]){
			splay(x);
			si[x]+=s[rc];
			si[x]-=s[rc=y];
		}
	}
	inline int findroot(R x){
		access(x);splay(x);
		while(lc)x=lc;
		splay(x);
		return x;
	}
	I link(R x){//隻傳一個參數，因為隻會連父邊，cut同理
		splay(x);//不用access(x)，因為x一定是連通塊的根
		R y=f[x]=fa[x];
		access(y);splay(y);//與正常LCT不同，别忘加
		si[y]+=s[x];s[y]+=s[x];
	}
	I cut(R x){
		access(x);splay(x);
		lc=f[lc]=0;
		pushup(x);
	}
}lct[2];
void dfs(R x){
	for(R y,i=he[x];i;i=ne[i])
		if((y=to[i])!=fa[x])
			fa[y]=x,dfs(y),lct[0].link(y);
}
#define G ch=getchar()
#define in(z) G;\
	while(ch<'-')G;\
	z=ch&15;G;\
	while(ch>'-')z*=10,z+=ch&15,G
int main(){
	register char ch;
	R p=1,n,m,i,u,v,op;
	in(n);
	for(i=1;i<n;++i){
		in(u);in(v);
		to[++p]=v;ne[p]=he[u];he[u]=p;
		to[++p]=u;ne[p]=he[v];he[v]=p;
	}
	dfs(1);
	fa[1]=n+1;lct[0].link(1);//虛點
	in(m);
	while(m--){
		in(op);in(u);
		if(op)lct[C].cut(u),lct[C^=1].link(u);
		else{
			v=lct[C].findroot(u);
			printf("%d\n",lct[C].s[lct[C].c[v][1]]);
		}
	}
    return 0;
}