CF1009F

, ,

Description

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

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

Solution

令 $f_{i,j}$ 表示 $i$ 的子树中，$d(i,x)=j$ 的个数。

容易想到 $f_{i,j}=\sum f_{son,j-1}$

以深度为下标，考虑长链剖分优化。用指针写比较方便（似乎也比较快（？））

dp 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void solve(int x,int pre) {
	int i,j;
	f[x][ans[x]=0]=1;//初始化
	if (son[x]) f[son[x]]=f[x]+1,solve(son[x],x);//继承
	else return;
	ans[x]=ans[son[x]]+1;
	if (f[x][ans[x]]<=1) ans[x]=0;
	for (i=h[x];i;i=a[i].z)
	    if (a[i].to!=pre&&a[i].to!=son[x]) {
	    	f[a[i].to]=id;id+=2*d[a[i].to];//分配内存
	    	solve(a[i].to,x);
	    	for (j=0;j<d[a[i].to];j++) {
	    		f[x][j+1]+=f[a[i].to][j];//暴力合并
	    		if (f[x][ans[x]]<f[x][j+1]||(j+1<=ans[x]&&f[x][ans[x]]==f[x][j+1])) ans[x]=j+1;//更新答案
			}
		}
}

code

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
#include<bits/stdc++.h>
#define maxn 1000005
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int son[maxn],d[maxn],head=1,h[maxn];
int *f[maxn],stac[maxn*2],n,*id=stac,ans[maxn];
struct yyy{
	int to,z;
	inline void add(int x,int y) {
		to=y;z=h[x];h[x]=head;
	}
}a[maxn*2];
inline void dfs1(int x,int pre) {
	int i;d[x]=1;
	for (i=h[x];i;i=a[i].z)
	    if (a[i].to^pre) {
	    	dfs1(a[i].to,x);
	    	if (d[x]<d[a[i].to]+1) d[x]=d[a[i].to]+1,son[x]=a[i].to;
		}
}
inline void solve(int x,int pre) {
	int i,j;
	f[x][ans[x]=0]=1;
	if (son[x]) f[son[x]]=f[x]+1,solve(son[x],x);
	else return;
	ans[x]=ans[son[x]]+1;
	if (f[x][ans[x]]<=1) ans[x]=0;
	for (i=h[x];i;i=a[i].z)
	    if (a[i].to!=pre&&a[i].to!=son[x]) {
	    	f[a[i].to]=id;id+=2*d[a[i].to];
	    	solve(a[i].to,x);
	    	for (j=0;j<d[a[i].to];j++) {
	    		f[x][j+1]+=f[a[i].to][j];
	    		if (f[x][ans[x]]<f[x][j+1]||(j+1<=ans[x]&&f[x][ans[x]]==f[x][j+1])) ans[x]=j+1;
			}
		}
}
signed main(void){
	int i,x,y;
	read(n);
	for (i=1;i<n;i++) {
		read(x);read(y);
		a[++head].add(x,y);
		a[++head].add(y,x);
	}
	dfs1(1,0);
	f[1]=id;id+=2*d[1];
	solve(1,0);
	for (i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}

似乎也可以用 dsu on tree 。