题意
一棵有根树，定义 $d_{u,i}$ 表示以 $u$ 为根的子树内离 $u$ 的距离为 $i$ 的节点个数。
对于每个节点 $u$，求出使 $d_{u,j}$ 最大的 $j$，且 $j$ 的编号最小。
$n\leq 10^6$
题解
$d_{u,i}=\sum_{v\in Son_u}d_{v,i-1}$
这个东东实现一次的复杂度是 $O(\sum_{v\in son_u}len_v)$ 的（其中 $len_v$ 为 $v$ 的子树中离 $v$ 的最远距离）。
可以用长链剖分解决。
如果我们用重儿子继承，即先算重儿子的 $d$ 值，那么 $d_{u,i}=d_{son_u,i-1}$。
相当于数组移动了 $1$ 位。那么用指针实现，令 $f_{son_u}=f_{u}+1$ 即可。
每个长链只会被统计一次答案，且统计的时间为长链的长。
因此复杂度是 $O(n)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000010
inline int read()
{
int x=0; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x;
}
int n,ans[N];
int ver[N<<1],ne[N<<1],head[N],tot;
inline void add(int x,int y)
{
ver[++tot]=y; ne[tot]=head[x]; head[x]=tot;
ver[++tot]=x; ne[tot]=head[y]; head[y]=tot;
}
int len[N],son[N];
int tmp[N],*f[N],*id=tmp;
void dfs1(int u,int pre)
{
for(int i=head[u],v;i;i=ne[i])
if((v=ver[i])!=pre)
{
dfs1(v,u);
if(len[son[u]]<len[v]) son[u]=v;
}
len[u]=len[son[u]]+1;
}
void dfs2(int u,int pre)
{
f[u][0]=1;
if(son[u]) f[son[u]]=f[u]+1,dfs2(son[u],u),ans[u]=ans[son[u]]+1;
for(int i=head[u],v;i;i=ne[i])
if((v=ver[i])!=pre&&ver[i]!=son[u])
{
f[v]=id; id+=len[v];
dfs2(v,u);
for(int j=0;j<len[v];j++)
{
f[u][j+1]+=f[v][j];
if(f[u][ans[u]]<f[u][j+1]||(f[u][ans[u]]==f[u][j+1]&&ans[u]>j+1)) ans[u]=j+1;
}
}
if(f[u][ans[u]]==1) ans[u]=0;
}
int main()
{
n=read();
for(int i=1;i<n;i++) add(read(),read());
dfs1(1,0);
f[1]=id; id+=len[1];
dfs2(1,0);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
|