XI.[BJOI2014]大融合

終于來了……我們終于要用LCT來維護子樹信息了。

因為我們看到，LCT是通過將原樹拆成一堆鏈而起效的。在樹鏈剖分中，我們通過dfs序來訪問一棵子樹；但是因為LCT的鏈是動態變化的，因此并沒有一組固定的訪問順序。

那怎么辦呢？

我們考慮最原始的想法：對于每個節點，再額外維護所有虛子節點的狀態。比如說，本題我們維護的就是虛子節點的子樹大小之和。

我們設 t[x].s1 表示一個節點所有子節點（不管虛實）的子樹大小之和，即在原樹中，它自己的子樹大小。再設 t[x].s2 為所有虛子節點的大小之和。

那么，pushup 函數將會長成這樣：

void pushup(int x){
	t[x].s1=t[x].s2+t[lson].s1+t[rson].s1+1;
}

我們再考慮其它函數會有什么變化。顯然，只有當節點間的虛實關系（邊由實轉序、連邊、斷邊等）發生變化時，s2 才會發生變化。

splay 函數：在同一棵實splay中操作，沒有虛實關系變化。

access 函數：有變化！

我們拎出來 access 函數：

void access(int x){
	for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}

可以看到，我們有 rson=y ，虛實關系產生了變化！！！

對于\(rson\)，這是實轉虛，s2 應該加上\(rson\)的 s1 ；對于\(y\)，這是虛轉實，s2 應該減去\(y\)的 s1 。

因此我們最終有：

void access(int x){
	for(int y=0;x;x=t[y=x].fa)splay(x),t[x].s2+=t[rson].s1-t[y].s1,rson=y,pushup(x);
}

makeroot ， findroot， split 函數：并沒有虛實變化（變化全在函數內調用的 access 函數，已經在 access 時改過了），沒有變化。

link ：情況有變！我們這時必須要將\(y\)的 s2 加上\(x\)的 s1 ，因為\(x\)成為了\(y\)的虛兒子！

但是，\(y\)一變，\(y\)的父親也要跟著變，\(y\)的爺爺也是……

我們有辦法。直接將\(y\) access 后移到\(root\)（注意是splay的\(root\)，不是整棵樹的\(ROOT\)），這樣\(y\)就沒有父親了！

因此我們的 link 函數就變成了這樣：

void link(int x,int y){
	split(x,y);
	t[y].s2+=t[x].s1;
	t[x].fa=y;
    pushup(y);
}

等等，哪來的 split ？

偷懶一下，我們只是把 makeroot(x),access(y),splay(y) 三合一。實際上\(x\)和\(y\)并不連通。

至于 cut ，這題并不需要。不過代碼還是放出來：

void cut(int x,int y){
	split(x,y);
  	t[x].fa=t[y].ch[0]=0;
	pushup(y);
}

然后，當我們要求出一個節點\(x\)的子樹大小時：

int query(int x,int y){
	split(x,y);
	return t[x].s1;
}

其中\(y\)就是指定的\(x\)的父親（不然不知道是哪顆子樹），在這題中就是給定詢問的邊的另一端點。

完整版放出：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m;
struct node{
	int ch[2],s1,s2,fa;
	bool rev;
}t[100100];
int identify(int x){
	if(t[t[x].fa].ch[0]==x)return 0;
	if(t[t[x].fa].ch[1]==x)return 1;
	return -1;
}
void pushup(int x){
	t[x].s1=t[x].s2+t[lson].s1+t[rson].s1+1;
}
void REV(int x){
	t[x].rev^=1,swap(lson,rson);
}
void pushdown(int x){
	if(!t[x].rev)return;
	if(lson)REV(lson);
	if(rson)REV(rson);
	t[x].rev=0;
}
void rotate(int x){
	int y=t[x].fa;
	int z=t[y].fa;
	int dirx=identify(x);
	int diry=identify(y);
	int b=t[x].ch[!dirx];
	if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
	if(b)t[b].fa=y;t[y].ch[dirx]=b;
	t[x].ch[!dirx]=y,t[y].fa=x;
	pushup(y),pushup(x);
}
void pushall(int x){
	if(identify(x)!=-1)pushall(t[x].fa);
	pushdown(x);
}
void splay(int x){
	pushall(x);
	while(identify(x)!=-1){
		int fa=t[x].fa;
		if(identify(fa)==-1)rotate(x);
		else if(identify(fa)==identify(x))rotate(fa),rotate(x);
		else rotate(x),rotate(x);
	}
}
void access(int x){
	for(int y=0;x;x=t[y=x].fa)splay(x),t[x].s2+=t[rson].s1-t[y].s1,rson=y,pushup(x);
}
void makeroot(int x){
	access(x),splay(x),REV(x);
}
int findroot(int x){
	access(x),splay(x);
	pushdown(x);
	while(lson)x=lson,pushdown(x);
	splay(x);
	return x;
}
void split(int x,int y){
	makeroot(x),access(y),splay(y);
}
void link(int x,int y){
	split(x,y);
	t[y].s2+=t[x].s1;
	t[x].fa=y;
}
int query(int x,int y){
	split(x,y);
	return t[x].s1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++){
		char s[10];
		scanf("%s%d%d",s,&x,&y);
		if(s[0]=='A')link(x,y);
		else printf("%lld\n",1ll*query(x,y)*query(y,x));
	}
	return 0;
}

總結

以上是生活随笔為你收集整理的[BJOI2014]大融合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。