[BJOI2014] 大融合 - LCT 维护子树信息

Description

一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。随着边的添加，动态的回答对于某些边的负载的询问。

Solution

回顾一下 LCT 是如何维护子树信息的

对 lct 上每个结点，维护两个 sz 和 si，前者维护该点的信息和，后者维护该点所有虚儿子的信息

access 操作时，将旧虚儿子从 si 中减去，将新虚儿子加入

link f[x]=y 后，将 x 的信息计入 si[y] 中（注意用 access）

pushup 时，按照上述公式更新一下即可

现在回到本题，需要询问的时候，我们先将这条边断开，然后查一下两边根点的答案即可

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

int n,m,val[N];

namespace lct{
	int top, q[N], ch[N][2], fa[N], rev[N];
	int sz[N], si[N];
	inline void pushup(int x){
		sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+si[x]+1; //
	}
	inline void pushdown(int x){
		if(!rev[x]) return;
		rev[ch[x][0]]^=1;
		rev[ch[x][1]]^=1;
		rev[x]^=1;
		swap(ch[x][0],ch[x][1]);
	}
	inline bool isroot(int x){
		return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
	}
	inline void rotate(int p){
		int q=fa[p], y=fa[q], x=ch[fa[p]][1]==p;
		ch[q][x]=ch[p][x^1]; fa[ch[q][x]]=q;
		ch[p][x^1]=q; fa[q]=p; fa[p]=y;
		if(y) if(ch[y][0]==q) ch[y][0]=p;
		else  if(ch[y][1]==q) ch[y][1]=p;
		pushup(q); pushup(p);
	}
	inline void splay(int x){
		q[top=1]=x;
		for(int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
		for(int i=top;i;i--) pushdown(q[i]);
		for(;!isroot(x);rotate(x))
			if(!isroot(fa[x]))
				rotate((ch[fa[x]][0]==x)==(ch[fa[fa[x]]][0]==fa[x])?fa[x]:x);
	}
	void access(int x){
		for(int t=0;x;t=x,x=fa[x])
			splay(x),si[x]+=sz[ch[x][1]],si[x]-=sz[t],ch[x][1]=t,pushup(x); //
	}
	void makeroot(int x){
		access(x);
		splay(x);
		rev[x]^=1;
	}
	int find(int x){
		access(x);
		splay(x);
		while(ch[x][0]) x=ch[x][0];
		return x;
	}
	void split(int x,int y){
		makeroot(x);
		access(y);
		splay(y);
	}
	void cut(int x,int y){
		split(x,y);
		if(ch[y][0]==x)
			ch[y][0]=0, fa[x]=0;
        pushup(y); //
	}
	void link(int x,int y){
		split(x,y); // !!!
		fa[x]=y;
		si[y]+=sz[x]; //
		pushup(y); //
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) lct::sz[i]=1;
	for(int i=1;i<=m;i++){
		char str[10]; int t1,t2;
		scanf("%s%d%d",&str,&t1,&t2);
		if(str[0]==‘A‘)
			lct::link(t1,t2);
		if(str[0]==‘Q‘) {
            lct::cut(t1,t2);
            lct::makeroot(t1);
            lct::makeroot(t2);
            cout<<1ll*lct::sz[t1]*lct::sz[t2]<<endl;
            lct::link(t1,t2);
		}
	}
}

[BJOI2014] 大融合 - LCT 维护子树信息

原文：https://www.cnblogs.com/mollnn/p/13180286.html