题目链接
题目大意：
给定一棵树，对于树上每个结点，将它删去，然后你可以将得到的森林中任意一棵树的一个点与其父亲断开并连接到另一颗树上。求森林中所有树
size
最大值的最小值。
先考虑怎么求一个点的答案。令
sizei
表示点
i
的子树和，min表示森林中最小的树的大小，
max
表示森林中最大的树的大小。那么我们可以二分答案
ans
，问题就转化为最大的树中是否存在一个点
i
，使sizei min≤ans且
max−sizei≤ans
，即
max−ans≤sizei≤ans−min
。 注意二分的边界。
从根开始
dfs
一遍，维护
4
个map：
mappath
：从根到点
i
父亲所有点的
size
mapheaviest
：点
i
重儿子的子树中所有点的
size
maplight
：点
i
所有轻儿子的子树中所有点的
size
mapother
：除上述
map
中所有点之外其它点的
size
求点
i
的答案时，判断删去这个点后森林中最大的树是什么：
如果是点
i的重儿子，直接二分，在
mapheaviest
上查询即可求出答案。
如果是根，那么由于在从根到点
i
父亲路径上所有点
size在删去
i
后要减去
sizei，要特判一下。其他可以在
mapother
上查询。
接下来考虑怎么维护这
4
个map：
mappath
：
dfs
时更新，退出时删除即可。
mapheaviset , maplight
：可以用树上启发式合并求。
mapother
：初始时所有点都在内，其他
map
中加入一个点时就删除这个点。
时间复杂度
O(nlogn)
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
#define N 100010
#define It map<int,int>::iterator
vector<int>g[N];
map<int,int>M[
4];
int i,j,k,n,m,p,sz[N],Ans[N],s[N],x,y,mn[N],smx[N],Rt;
inline int Min(
int x,
int y){
return x<y?x:y;
}
inline int Max(
int x,
int y){
return x<y?y:x;
}
inline void Dfs1(
int x){
sz[x]=
1;mn[x]=n;
for(
int i=
0;i<g[x].size();i++){
Dfs1(g[x][i]);
sz[x]+=sz[g[x][i]];
mn[x]=Min(mn[x],sz[g[x][i]]);
if(sz[g[x][i]]>sz[s[x]])smx[x]=sz[s[x]],s[x]=g[x][i];
else
if(sz[g[x][i]]>smx[x])smx[x]=sz[g[x][i]];
}
M[
3][sz[x]]++;
if(sz[x]<n)mn[x]=Min(mn[x],n-sz[x]);
}
inline void Update(
int x,
int y,
int d){
M[d][x]+=y;M[
3][x]-=y;
if(!M[
3][x])M[
3].erase(x);
if(!M[d][x])M[d].erase(x);
}
inline void Get(
int x,
int y,
int d){
Update(sz[x],y,d);
for(
int i=
0;i<g[x].size();i++)Get(g[x][i],y,d);
}
inline int Find(
int x,
int y,
int l,
int r,
int d,
int z){
int Mid;
if(x==y&&x>=l&&x<=r)
return x;
while(l<=r){
Mid=l+r>>
1;
It t=M[d].lower_bound(y-Mid+z);
if(t!=M[d].end()&&t->first<=Mid-x+z)r=Mid-
1;
else l=Mid+
1;
}
return l;
}
inline void Solve(
int x){
if(sz[x]==n)Ans[x]=Find(mn[x],sz[s[x]],smx[x],sz[s[x]],
1,
0);
else
if(sz[s[x]]>n-sz[x])Ans[x]=Find(Min(mn[x],n-sz[x]),sz[s[x]],Max(n-sz[x],smx[x]),sz[s[x]],
1,
0);
else
if(!s[x])Ans[x]=n-sz[x];
else Ans[x]=Min(Find(mn[x],n-sz[x],sz[s[x]],n-sz[x],
0,sz[x]),Find(mn[x],n-sz[x],sz[s[x]],n-sz[x],
3,
0));
}
inline void Dfs(
int x,
bool d){
Update(sz[x],
1,
0);
for(
int i=
0;i<g[x].size();i++)
if(g[x][i]!=s[x])Dfs(g[x][i],
0);
if(s[x])Dfs(s[x],
1);
for(
int i=
0;i<g[x].size();i++)
if(g[x][i]!=s[x])Get(g[x][i],
1,
2);
if(!(--M[
0][sz[x]]))M[
0].erase(sz[x]);
Solve(x);
M[
3][sz[x]]++;
if(d){
Update(sz[x],
1,
1);
for(It t=M[
2].begin();t!=M[
2].end();)
M[
1][t->first]+=t->second,M[
2].erase(t++);
}
else for(
int i=
0;i<g[x].size();i++)
if(g[x][i]!=s[x])Get(g[x][i],-
1,
2);
else Get(g[x][i],-
1,
1);
}
int main(){
scanf(
"%d",&n);
if(n==
1)
return putchar(
48),
0;
for(i=
1;i<=n;i++){
scanf(
"%d%d",&x,&y);
if(x)g[x].push_back(y);
else Rt=y;
}
Dfs1(Rt);
Dfs(Rt,
1);
for(i=
1;i<=n;i++)
printf(
"%d\n",Ans[i]);
return 0;
}
