题目概述

CF1009F

解题报告

定义 $f_{i,j}$ 表示 $i$ 子树内到 $i$ 距离为 $j$ 的个数，则显然 $f_{i,0}=1,f_{i,j}=\sum_{u\in son(i)}f_{u,j-1}$ 。

利用长链剖分优化，长链中的 $f$ 共享，然后将短链中的 $f$ 暴力合并到长链中即可。

每条链只会合并一次，且所有长链的总长度为 $n$ ，因此复杂度 $O(n)$ 。

可以利用指针实现长链 $f$ 共享，因为长链中儿子的 $f$ 是由父亲的 $f$ 右移一位得到。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
const int maxn=1000000;

int n,dep[maxn+5],md[maxn+5],SH[maxn+5],len[maxn+5];
int tem[(maxn<<1)+5],*pl=tem,*f[maxn+5],ans[maxn+5];
int E,lnk[maxn+5],nxt[(maxn<<1)+5],to[(maxn<<1)+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[1<<16],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,1<<16,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
    int si;char buf[1<<16];
    fastO() {si=0;}
    void putc(char ch){
        if (si==(1<<16)) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
    static int len=0,buf[100];
    if (x<0) fo.putc('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) fo.putc(buf[--len]+48);
    if (ch) fo.putc(ch);
}
inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void DFS(int x,int pre=0){
    dep[x]=dep[pre]+1;md[x]=dep[x];
    for (int j=lnk[x];j;j=nxt[j])
        if (to[j]!=pre){
            DFS(to[j],x);
            if (md[to[j]]>md[x]) md[x]=md[to[j]],SH[x]=to[j];
        }
    len[x]=len[SH[x]]+1;
}
void DP(int x,int pre=0,bool fl=true){
    if (fl) f[x]=pl,pl+=len[x]+1;
    f[x][0]++;
    if (SH[x]) f[SH[x]]=f[x]+1,DP(SH[x],x,false),ans[x]=ans[SH[x]]+1;
    for (int j=lnk[x],u;j;j=nxt[j])
        if ((u=to[j])!=pre && u!=SH[x]){
            DP(u,x,true);
            for (int j=0;j<=len[u];j++){
                f[x][j+1]+=f[u][j];
                if (f[x][j+1]>f[x][ans[x]] || f[x][j+1]==f[x][ans[x]] && j+1<ans[x]) ans[x]=j+1;
            }
        }
    if (f[x][ans[x]]<=1) ans[x]=0;
}
int main(){
    readi(n);
    for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
    DFS(1);DP(1);
    for (int i=1;i<=n;i++) writei(ans[i]);
    return 0;
}