Tang-Dreamoon's Blog

bzoj 1095 捉迷藏

发表于 | 分类于 ， ，

动态点分治

　　题目链接：bzoj 1095

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：给定一棵树，每个点有黑白两种颜色，求树上最远两个黑点之间的距离。这道题用动态点分治和边分治都可以解决，在这里我采用的是动态点分治的做法(其实这两个东西大同小异)。首先介绍一下动态点分治的思想：和点分治一样，我们通过不断寻找树的重心，将树不断的分成一块一块的然后将问题分治成一个个子问题然后递归进入子树即可。对于这道题而言，子问题就转化为了如何在一个以重心为根的子树内寻找两个最远黑点之间的距离 X，X 显然等于对所有子树的 X 和所有黑点到根的最大值加最小值取 Max。所以我们对于一个重心需要维护两个堆(或Set)，分别记录它的每个子树的最长链(堆①)和当前子树内的每个黑点到根的距离(堆②)。然后修改某个点的颜色就等于把它的 logn 个祖先的两个堆都进行修改维护——在堆中添加或删除元素。

　　我思故我在：我个人认为动态点分治有两个需要注意的事项：一是在维护当前子树的(堆②)时，我们记录的“距离”是每个点到当前子树的“原根”的距离而不是到当前子树的重心的距离；“原根”即为访问进入这个子树的那个点。还有就是对于两个堆的理解不够深入：当前子树的(堆②)，它虽然关联到了当前的重心节点上但它实际上是在为当前重心节点的“父亲”节点服务的。所以在修改这个堆的时候应该与它父亲的(堆①)一并修改。这时就要注意一个小细节，在修改点 X 的颜色时应该注意先把 X 的(堆①)独自修改完后再进行上述操作。

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
int n,m;
int all,mina,head;
vector<int> ve[100100];
multiset<int> se;
multiset<int> sa[100100];
multiset<int> sq[100100];
int maxa[100100];
int fa[100100],size[100100];
bool biao[100100],zhuang[100100];
struct table{
	int to,vl;
};
vector<table> va[100100];
void dfs(int x)
{
	size[x]=0;
	for(int i=0;i<ve[x].size();i++)
	{
		int y=ve[x][i];
		if(y!=fa[x]&&!biao[y])
		{
			fa[y]=x;
			dfs(y);
			size[x]+=size[y];
		}
	}
	size[x]++;
}
void getroot(int x)
{
	int maxa=-1;
	for(int i=0;i<ve[x].size();i++)
	{
		int y=ve[x][i];
		if(y!=fa[x]&&!biao[y])
		{
			getroot(y);
			maxa=max(maxa,size[y]);
		}
	}
	maxa=max(maxa,all-size[x]);
	if(maxa<mina)
		mina=maxa,head=x;
}
void suan(int x,int now,int hh)
{
	for(int i=0;i<ve[x].size();i++)
	{
		int y=ve[x][i];
		if(y!=fa[x]&&!biao[y])
		{
			sa[hh].insert(now+1),va[y].push_back((table){hh,now+1});
			suan(y,now+1,hh);
		}
	}
}
int fz(int x)
{
	fa[x]=x;
	dfs(x);
	all=size[x],mina=2147483647;
	getroot(x);
	int fuck=head;
	//cout<<fuck<<endl;
	sa[fuck].insert(0),va[x].push_back((table){fuck,0});
	for(int i=0;i<ve[x].size();i++)
	{
		int y=ve[x][i];
		if(!biao[y])
		{
			sa[fuck].insert(1),va[y].push_back((table){fuck,1});
			suan(y,1,fuck);
		}
	}
	biao[fuck]=1;
	sq[fuck].insert(0);
	for(int i=0;i<ve[fuck].size();i++)
	{
		int y=ve[fuck][i];
		if(!biao[y])
		{
			int p=fz(y);
			sq[fuck].insert(p+1);
		}
	}
	if(sq[fuck].size()>=2)
	{
		multiset<int> ::iterator it=sq[fuck].end();
		--it;
		maxa[fuck]=*it+*(--it);
		se.insert(maxa[fuck]);
	}
	//cout<<fuck<<" "<<maxa[fuck]<<endl;
	return *(--sa[fuck].end());
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		ve[x].push_back(y);
		ve[y].push_back(x);
	}
	se.insert(0);
//	cout<<"********"<<endl;
	fz(1);
	scanf("%d",&m);
	while(m--)
	{
		char ap[10];
		scanf("%s",ap+1);
		if(ap[1]=='G')
		{
			printf("%d\n",*(--se.end()));
		}
		else
		{
			int x;
			multiset<int> ::iterator it;
			scanf("%d",&x);
			if(maxa[x]!=0)
				it=se.find(maxa[x]),se.erase(it);
			if(zhuang[x]==0)
				sq[x].erase(0);
			else
				sq[x].insert(0);
			if(sq[x].size()>=2)
			{
				it=sq[x].end();
				--it;
				maxa[x]=*it+*(--it);
				se.insert(maxa[x]);
			}
			else maxa[x]=0;
			for(int i=va[x].size()-1;i>0;i--)
			{
				table y=va[x][i];
				table z=va[x][i-1];
				if(maxa[z.to]!=0)
					it=se.find(maxa[z.to]),se.erase(it);
				if(sa[y.to].size()>0)
					it=sq[z.to].find(*(--sa[y.to].end())+1),sq[z.to].erase(it);
				if(zhuang[x]==0)
				{
					it=sa[y.to].find(y.vl);
					sa[y.to].erase(it);
				}
				else
				{
					sa[y.to].insert(y.vl);
				}
				if(sa[y.to].size()>0)
					sq[z.to].insert(*(--sa[y.to].end())+1);
				if(sq[z.to].size()>=2)
				{
					it=sq[z.to].end();
					--it;
					maxa[z.to]=*it+*(--it);
					se.insert(maxa[z.to]);
				}
				else maxa[z.to]=0;
			}
			zhuang[x]=zhuang[x]^1;
		}
	}
	return 0;
}