原题链接

题目翻译

给定一棵以 $1 $为根，$n(1 \leq n \leq 10^6)$个节点的树。设 $d(u,x) $为 $u $子树中到 $u$ 距离为$ x$ 的节点数。

对于每个点，求一个最小的 $k$，使得$d(u,k)$ 最大。

输入格式

第一行包含一个整数$n$
接下来n-1行每行两个数$x$，$y$表示$x$，$y$之间有一条边

输出格式

$n$行，最小的$k$值

题目分析

按照深度建立权值线段树即可其他与 雨天的尾巴 类似，详细看雨天的尾巴题解

//时间O(nlogn)——3587ms 空间——430400KB
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000010;
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int n,dep[N],M;
void dfs1(int u,int fa)
{
    dep[u]=dep[fa]+1;
    M=max(M,dep[u]);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dfs1(j,u);
    }
}
struct node
{
    int l,r;
    int val;
}tree[N*30];//开20会T 40会炸空间
int root[N],cnt;
void insert(int &u,int l,int r,int d)
{
    if(!u) u=++cnt;
    if(l==r) 
    {
        tree[u].val++;
        return;
    }
    int mid=l+r>>1;
    if(d<=mid) insert(tree[u].l,l,mid,d);
    else insert(tree[u].r,mid+1,r,d);
    tree[u].val=max(tree[tree[u].l].val,tree[tree[u].r].val);
}
int merge(int x,int y,int l,int r)
{
    if(!x||!y) return x+y;
    if(l==r)
    {
        tree[x].val+=tree[y].val;
        return x;
    }
    int mid=l+r>>1;
    tree[x].l=merge(tree[x].l,tree[y].l,l,mid);
    tree[x].r=merge(tree[x].r,tree[y].r,mid+1,r);
    tree[x].val=max(tree[tree[x].l].val,tree[tree[x].r].val);
    return x;
}
int query(int u,int l,int r)
{
    if(!u) return 0;
    if(l==r) return l;
    int mid=l+r>>1;
    if(tree[tree[u].l].val>=tree[tree[u].r].val) return query(tree[u].l,l,mid);
    else return query(tree[u].r,mid+1,r);
}
int ans[N];
void dfs2(int u,int fa)
{
    insert(root[u],1,M,dep[u]);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dfs2(j,u);
        root[u]=merge(root[u],root[j],1,M);
    }

    ans[u]=query(root[u],1,M)-dep[u];
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<n;i++) 
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
    return 0;
}