题意
给定一棵 $n$ 个点的树以及 $q$ 次操作. 操作有两种, 一种是求有效点之间的最大距离, 另一种是将一个点的有效状态反转.
$n\le 1\times 10^5,q\le 5\times 10^5$.
题解
好像老老实实写动态点分的在榜上都垫底了qaq
我们可以发现这个求两点之间最大距离非常的点分治, 为了处理修改有效点的问题, 我们需要动态点分治.
首先我们把点分树建出来, 接下来的操作对点分树进行(距离按原树算).
然后对于每个点, 我们记录两个平衡树/堆, 一个 $len$ 表示这个子树中的所有点到根的父亲的距离, 一个 $maxd$ 表示各个子结点的 $len$ 中的最大值. 全局再维护一个 $all$ 存储每个点的 $maxd$ 中的最大值与次大值之和.
不难发现每次查询的时候取 $all$ 中的最大值即是答案.
修改的时候距离用LCA计算, 每次先把当前点可能产生的贡献删除, 修改后再插回去.
初始化的时候有个技巧, DFS当前分治子树的时候 $dis[root]$ 保存的是父分治子树的根到当前点的距离. 发现这刚好就是我们要算的东西, 直接insert进set就好了.
复杂度 $O((n+q)\log^2 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
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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
#include <bits/stdc++.h>
const int MAXV=1e5+10;
const int MAXE=2e5+10;
typedef std::multiset<int,std::greater<int>> multiset;
struct Edge{
int from;
int to;
Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* topE=E;
int n;
int q;
int root;
int cursize;
int prt[MAXV];
int dis[MAXV];
int top[MAXV];
int son[MAXV];
int size[MAXV];
int pprt[MAXV];
int deep[MAXV];
bool off[MAXV];
bool vis[MAXV];
int msize[MAXV];
multiset all;
multiset len[MAXV];
multiset maxd[MAXV];
char GetCmd();
int ReadInt();
void Solve(int);
int Dis(int,int);
int LCA(int,int);
void DFS(int,int);
void Insert(int,int);
void Modify(int,bool);
void DFS(int,int,int);
void GetRoot(int,int);
int Export(const multiset&);
int main(){
n=ReadInt();
for(int i=1;i<n;i++){
int a=ReadInt(),b=ReadInt();
Insert(a,b);
Insert(b,a);
}
DFS(1,0,0);
DFS(1,1);
cursize=n;
msize[0]=n;
GetRoot(1,0);
Solve(root);
q=ReadInt();
while(q--){
if(GetCmd()=='C'){
int x=ReadInt();
Modify(x,off[x]^=1);
}
else
printf("%d\n",*all.begin());
}
return 0;
}
void Modify(int x,bool opt){
if(maxd[x].size()>1)
all.erase(all.find(Export(maxd[x])));
if(opt)
maxd[x].erase(maxd[x].find(0));
else
maxd[x].insert(0);
if(maxd[x].size()>1)
all.insert(Export(maxd[x]));
for(int p=x;prt[p]!=0;p=prt[p]){
if(maxd[prt[p]].size()>1)
all.erase(all.find(Export(maxd[prt[p]])));
if(!len[p].empty())
maxd[prt[p]].erase(maxd[prt[p]].find(*len[p].begin()));
if(opt)
len[p].erase(len[p].find(Dis(prt[p],x)));
else
len[p].insert(Dis(prt[p],x));
if(!len[p].empty())
maxd[prt[p]].insert(*len[p].begin());
if(maxd[prt[p]].size()>1)
all.insert(Export(maxd[prt[p]]));
}
}
void DFS(int root,int prt,multiset& len){
if(dis[root]!=0)
len.insert(dis[root]);
dis[root]=dis[prt]+1;
for(Edge* i=head[root];i!=NULL;i=i->next)
if(i->to!=prt&&!vis[i->to])
DFS(i->to,root,len);
}
void Solve(int root){
vis[root]=true;
if(dis[root]!=0)
len[root].insert(dis[root]);
dis[root]=0;
for(Edge* i=head[root];i!=NULL;i=i->next){
if(!vis[i->to])
DFS(i->to,root,len[root]);
}
maxd[root].insert(0);
for(Edge* i=head[root];i!=NULL;i=i->next){
if(!vis[i->to]){
::root=0;
cursize=size[i->to];
GetRoot(i->to,root);
int son=::root;
prt[son]=root;
Solve(son);
if(!len[son].empty())
maxd[root].insert(*len[son].begin());
}
}
if(maxd[root].size()>1)
all.insert(Export(maxd[root]));
}
void GetRoot(int root,int prt){
size[root]=1;
msize[root]=0;
for(Edge* i=head[root];i!=NULL;i=i->next){
if(!vis[i->to]&&i->to!=prt){
GetRoot(i->to,root);
size[root]+=size[i->to];
msize[root]=std::max(msize[root],size[i->to]);
}
}
msize[root]=std::max(msize[root],cursize-size[root]);
if(msize[root]<msize[::root])
::root=root;
}
inline void Insert(int from,int to){
topE->from=from;
topE->to=to;
topE->next=head[from];
head[from]=topE++;
}
void DFS(int root,int prt,int deep){
size[root]=1;
pprt[root]=prt;
::deep[root]=deep;
for(Edge* i=head[root];i!=NULL;i=i->next){
if(i->to!=prt){
DFS(i->to,root,deep+1);
size[root]+=size[i->to];
if(size[i->to]>size[son[root]])
son[root]=i->to;
}
}
}
void DFS(int root,int top){
::top[root]=top;
if(son[root])
DFS(son[root],top);
for(Edge* i=head[root];i!=NULL;i=i->next)
if(i->to!=pprt[root]&&i->to!=son[root])
DFS(i->to,i->to);
}
inline int Dis(int x,int y){
return deep[x]+deep[y]-2*(deep[LCA(x,y)]);
}
inline int LCA(int x,int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])
std::swap(x,y);
x=pprt[top[x]];
}
if(deep[x]>deep[y])
std::swap(x,y);
return x;
}
inline int ReadInt(){
int x=0;
register char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
inline char GetCmd(){
register char ch=getchar();
while(ch!='C'&&ch!='G')
ch=getchar();
return ch;
}
inline int Export(const multiset& s){
auto it=s.begin();
++it;
return *s.begin()+*it;
}
|
