长链剖分洛谷dominant indices

悠悠 2023-06-03 05:52 16阅读 0赞

## 题意翻译 ##

给出一棵有根树，对于每个节点x，定义一个无穷序列d，其中d(x,i)表示以x为根节点的子树中到x的距离恰好为i的点的个数，i=0~无穷，现在对每个点x，希望求出一个东西j，使得对于任意k<j，d(x,k)<d(x,j)，对于任意k>j,d(x,k)<=d(x,j)

输入格式： 第一行一个整数n，表示树的节点个数 接下来n-1行，每行两个整数，x，y，表示x,y之间有一条连边

输出格式： n行，每行一个整数，第i行表示x=i时对应的j

## 输入输出样例 ##

**输入 \#1**复制

4
    1 2
    2 3
    3 4

**输出 \#1**复制

0
    0
    0
    0

**输入 \#2**复制

4
    1 2
    1 3
    1 4

**输出 \#2**复制

1
    0
    0
    0

**输入 \#3**复制

4
    1 2
    2 3
    2 4

**输出 \#3**复制

2
    1
    0
    0

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    using namespace std;
    int gi(){
        int x=0,w=1;char ch=getchar();
        while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
        if (ch=='-') w=0,ch=getchar();
        while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
        return w?x:-x;
    }
    const int N = 1e6+5;
    int n,to[N<<1],nxt[N<<1],head[N],cnt;
    int len[N],son[N],tmp[N],*f[N],*id=tmp,ans[N];
    void link(int u,int v){
        to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
        to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
    }
    void dfs(int u,int ff){
        for (int e=head[u];e;e=nxt[e])
            if (to[e]!=ff){
                dfs(to[e],u);
                if (len[to[e]]>len[son[u]]) son[u]=to[e];
            }
        len[u]=len[son[u]]+1;
    }
    void dp(int u,int ff){
        f[u][0]=1;
        if (son[u])
            f[son[u]]=f[u]+1,dp(son[u],u),ans[u]=ans[son[u]]+1;
        for (int e=head[u];e;e=nxt[e]){
            int v=to[e];if (v==ff||v==son[u]) continue;
            f[v]=id;
            id+=len[v];
            dp(v,u);
            for (int j=1;j<=len[v];++j){
                f[u][j]+=f[v][j-1];
                if ((j<ans[u]&&f[u][j]>=f[u][ans[u]])||(j>ans[u]&&f[u][j]>f[u][ans[u]]))
                    ans[u]=j;
            }
        }
        if (f[u][ans[u]]==1) ans[u]=0;
    }
    int main(){
        n=gi();
        for (int i=1;i<n;++i) link(gi(),gi());
        dfs(1,0);
    //    for(int i=1;i<=n;i++)cout<<i<<" "<<len[i]<<" "<<son[i]<<endl;
        f[1]=id;
        id+=len[1];
        dp(1,0);
        for (int i=1;i<=n;++i) printf("%d\n",ans[i]);
        return 0;
    }