【gdgzezoi】Problem C: The Winds of Winter

商天逸

2023-12-01

Description

给定一棵n个点的树，对于树上每个结点，将它删去，然后可以将得到的森林中任意一个点与其父亲断开并连接到另一颗树上，对每一个点求出森林中所有树size最大值的最小值。

Input

第一行，一个数n。

第2~n+1行，每行两个整数x,y，(1<=x<=y<=n)，表示x是y的父亲（若x=0则y为根）。

Output

共n行，每行一个数，第i行表示删去点i后的答案。

Sample Input

0 1

1 2

1 3

1 4

2 5

2 6

3 7

4 8

4 9

5 10

Sample Output

Hint

10%的数据，n<=10

30%的数据，n<=10^3

100%的数据，n<=10^5

思路

先考虑怎么求一个点的答案。令size[i]表示点i的子树和，min表示森林中最小的树的大小，max表示森林中最大的树的大小。那么我们可以二分答案ans，问题就转化为最大的树中是否存在一个点i，使size[i]+min≤ans且max−size[i]≤ans，即max−ans≤size[i]≤ans−min。
注意二分的边界。

从根开始dfs一遍，维护4个map：

mappath：从根到点i父亲所有点的size

mapheaviest：点i重儿子的子树中所有点的size

maplight：点i所有轻儿子的子树中所有点的size

mapother：除上述map中所有点之外其它点的size

求点i的答案时，判断删去这个点后森林中最大的树是什么：

如果是点i的重儿子，直接二分，在mapheaviest上查询即可求出答案。

如果是根，那么由于在从根到点i父亲路径上所有点size在删去i后要减去size[i]，要特判一下。其他可以在mapother上查询。

接下来考虑怎么维护这4个map：

mappath：dfs时更新，退出时删除即可。

mapheaviset , maplight：可以用树上启发式合并求。

mapother：初始时所有点都在内，其他map中加入一个点时就删除这个点。

时间复杂度O(nlogn)

代码

#include<bits/stdc++.h>
using namespace std;
#define it map<int,int>::iterator 
map<int,int> mp[4];
vector<int> v[100010];
int size[100010],son[100010],mn[100010],mx2[100010],ans[100010],n,m,rt;
void add(int x,int y,int hh)
{
    mp[hh][x]+=y;mp[3][x]-=y;
    if (!mp[3][x]) mp[3].erase(x);
    if (!mp[hh][x]) mp[hh].erase(x);
}
  
void insert(int x,int y,int hh)
{
    add(size[x],y,hh);
    for (int i=0;i<v[x].size();i++) insert(v[x][i],y,hh);
}
  
int find(int x,int y,int l,int r,int hh,int z)
{
    if (x==y&&x>=l&&x<=r) return x;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        it t=mp[hh].lower_bound(y-mid+z);
        if (t!=mp[hh].end()&&t->first<=mid-x+z) r=mid-1;
        else l=mid+1;
    }
    return l;
}
  
void work(int x)
{
    if (size[x]==n) ans[x]=find(mn[x],size[son[x]],mx2[x],size[son[x]],1,0);
    else if (size[son[x]]>n-size[x]) ans[x]=find(min(mn[x],n-size[x]),size[son[x]],max(n-size[x],mx2[x]),size[son[x]],1,0);
    else if (!son[x]) ans[x]=n-size[x];
    else ans[x]=min(find(mn[x],n-size[x],size[son[x]],n-size[x],0,size[x]),find(mn[x],n-size[x],size[son[x]],n-size[x],3,0));
}
  
void pre(int x)
{
    size[x]=1;mn[x]=n;
    for (int i=0;i<v[x].size();i++)
    {
        pre(v[x][i]);
        size[x]+=size[v[x][i]];
        mn[x]=min(mn[x],size[v[x][i]]);
        if (size[v[x][i]]>size[son[x]]) mx2[x]=size[son[x]],son[x]=v[x][i];
        else if (size[v[x][i]]>mx2[x]) mx2[x]=size[v[x][i]];
    }
    mp[3][size[x]]++;
    if (size[x]<n) mn[x]=min(mn[x],n-size[x]);
}
  
void dfs(int x,bool bo)
{
    add(size[x],1,0);
    for (int i=0;i<v[x].size();i++) if (v[x][i]!=son[x]) dfs(v[x][i],0);
    if (son[x]) dfs(son[x],1);
    for (int i=0;i<v[x].size();i++) if (v[x][i]!=son[x]) insert(v[x][i],1,2);
    if (!(--mp[0][size[x]])) mp[0].erase(size[x]);
    work(x);
    mp[3][size[x]]++;
    if (bo)
    {
        add(size[x],1,1);
        for (it t=mp[2].begin();t!=mp[2].end();)
        {
            mp[1][t->first]+=t->second;
            mp[2].erase(t++);
        }
    }
    else for (int i=0;i<v[x].size();i++)
    {
        int t=v[x][i];
        if (t!=son[x]) insert(t,-1,2);
        else insert(t,-1,1);
    }
}
  
int main()
{
    scanf("%d",&n);
    if (n==1) { puts("0");return 0; }
    for (int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if (x) v[x].push_back(y);
        else rt=y;
    }
    pre(rt);dfs(rt,1);
    for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}