洛谷P4219 lct维护子树信息

题意：

给出$n$个独立的点，处理以下$q$个操作，每个操作只会是如下操作之一

（1）连接$x,y$，保证原本没有边存在

（2）查询边$(x,y)$的负荷，定义负荷为树上经过$(x,y)$的简单路径的个数

$LCT$维护（原树中）子树信息

设$size$是当前结点为根的情况下的子树信息和，$vsize(virtual\_size)$是当前结点为根的情况下的所有虚儿子的子树和。

如果给定根，即已知$x$的父节点$fa$，那么只需要$split(x,fa)$，$x$的$vsize$就已经是原树的子树信息和了。

更一般的，$size$维护的是原树这个图的连接的所有连通分量的信息和，如果给定根要找出子树信息和，只需要剥离他的父亲即可。

另外，在维护子树信息时，$link(x,y)$时，最好先$splay(y)$。因为$y$也有父亲，给$y$连接了虚儿子后，也需要$push\_upy$的父亲，先$splay(y)$后，$y$就没有父亲了，也就不需要更新。

也可以在连接虚儿子后$splay(y)$，此时的含义就是手动更新$y$的祖先们。

维护子树信息只需要在更改了虚实关系的函数更新$vsize$即可，仅需在$link,access$中更新

#include
#define ll long long
using namespace std;

struct LCT
{
	struct node
	{
		int v,tag,son[2],fa,size,vsize;
	};
	stack<int>s;
	vector<node>tree;
	LCT():tree(100005){}
	bool isroot(int x)
	{
		return tree[tree[x].fa].son[0]!=x&&tree[tree[x].fa].son[1]!=x;
	}
	int getson(int x,int y)
	{
		return x==tree[y].son[1];
	}
	void push_up(int x)
	{
		tree[x].size=1+tree[x].vsize+tree[tree[x].son[0]].size+tree[tree[x].son[1]].size;
	}
	void rotate(int x)
	{
		int y=tree[x].fa,z=tree[y].fa;
		int k1=getson(x,y),k2=getson(y,z);
		tree[x].fa=z;
		if(!isroot(y)) tree[z].son[k2]=x;
		tree[y].son[k1]=tree[x].son[!k1];
		if(tree[x].son[!k1]) tree[tree[x].son[!k1]].fa=y;
		tree[x].son[!k1]=y;
		tree[y].fa=x;
		push_up(y); push_up(x);
	}
	void reverse(int x)
	{
		swap(tree[x].son[0],tree[x].son[1]);
		tree[x].tag^=1;
	}
	void push_down(int x)
	{
		if(!tree[x].tag) return;
		for(int i=0;i<=1;i++)
			if(tree[x].son[i]) reverse(tree[x].son[i]);
		tree[x].tag=0;
	}
	void splay(int x)
	{
		int now=x;
        push_up(now);
		s.push(now);
		while(!isroot(now))
		{
			s.push(tree[now].fa);
            // push_up(tree[now].fa);
			now=tree[now].fa;
		}
		while(!s.empty())
		{
			push_down(s.top());
			s.pop();
		}
		while(!isroot(x))
		{
			int y=tree[x].fa,z=tree[y].fa;
			int k1=getson(x,y),k2=getson(y,z);
			if(!isroot(y))
			{
				if(k1==k2) rotate(y);
				else rotate(x);
			}
			rotate(x);
		}
	}
	void access(int x)//打通root->x的splay
	{
		int last=0;
		while(x)
		{
			splay(x);
            tree[x].vsize+=tree[tree[x].son[1]].size-tree[last].size;
			tree[x].son[1]=last;
			push_up(last=x);
			x=tree[x].fa;
		}
	}
	void makeroot(int x)
	{
		access(x);
		splay(x);
		reverse(x);
	}
	int findroot(int x)
	{
		access(x);
		splay(x);
		while(tree[x].son[0])
		{
			push_down(x);
			x=tree[x].son[0];
		}
		splay(x);
		return x;
	}
	void split(int x,int y)
	{
		makeroot(x);
		access(y);
		splay(y);
	}
	void link(int x,int y)
	{
		makeroot(x);
		if(x==findroot(y)) return;
        splay(y);
		tree[x].fa=y;
        tree[y].vsize+=tree[x].size;
        push_up(y);
	}
	// void cut(int x,int y)
	// {
	// 	makeroot(x);
	// 	if(findroot(y)!=x||tree[y].fa!=x||tree[y].son[0]) return;
	// 	tree[y].fa=tree[x].son[1]=0;
	// }
}lct;

int n,q;

int main()
{
    scanf("%d%d",&n,&q);
    while(q--)
    {
        char s[5]; int x,y;
        scanf("%s%d%d",s+1,&x,&y);
        if(s[1]=='A') lct.link(x,y);
        else
        {
            lct.split(x,y);
            printf("%lld\n",1ll*(lct.tree[x].vsize+1)*(lct.tree[y].vsize+1));
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148