bzoj 4551 树

Posted on | Views:

并查集.

  • 大力用树剖 + 树状数组维护是 $O(n\cdot log^3n)$ 的.
  • 考虑先将操作先全部离线下来,每个标记都打上,对于没有被打标记的点,用并查集将它与它的父亲合并.
  • 然后从后往前处理操作,遇到询问就直接回答,遇到修改,其实是给某个点的标记次数 $-1$ ,删除后用并查集合并.
  • 时间复杂度 $O(n)$ .
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,Q;
char buf[2];
int head[MAXN],to[MAXN],nx[MAXN],ecnt=0;
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
struct opt
{
	int tp,x;
}q[MAXN];
struct dsu
{
	int fa[MAXN];
	void init()
	{
		for(int i=1;i<=n;++i)
			fa[i]=i;
	}
	int Find(int x)
	{
		if(x==fa[x])
			return x;
		return (fa[x]=Find(fa[x]));
	}
	void Merge(int u,int v)
	{
		u=Find(u),v=Find(v);
		if(u!=v)
			fa[u]=v;
	}
}DSU;
int flag[MAXN],Fa[MAXN];
void dfs(int u,int f)
{
	Fa[u]=f;
	if(!flag[u])
		DSU.Merge(u,f);
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		dfs(v,u);
	}
}
int ans[MAXN],tot=0;
int main()
{
	n=read(),Q=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
	}
	flag[1]=1;
	for(int i=1;i<=Q;++i)
	{
		scanf("%s",buf);
		q[i].tp=(buf[0]=='C');
		q[i].x=read();
		if(q[i].tp)
			++flag[q[i].x];
		else
			++tot;
	}
	int pt=tot;
	DSU.init();
	dfs(1,0);
	for(int i=Q;i>=1;--i)
	{
		int tp=q[i].tp,x=q[i].x;
		if(!tp)
		{
			x=DSU.Find(x);
			ans[pt--]=x;
		}
		else
		{
			--flag[x];
			if(!flag[x])
				DSU.Merge(x,Fa[x]);	
		}
	}
	for(int i=1;i<=tot;++i)
		printf("%d\n",ans[i]);
	return 0;
}