题意

给定一棵以 \(1\) 为根的树，你每次可以选择跳到某个叶子节点，再跳到和他深度差不超过 \(k\) 的祖先。询问最多能够跳到多少个叶子节点。

\(n,k\leq 10^6\) .

分析

• 最后的决策一定是跳很多叶子然后回到 \(u\) 后向下跳上不来。

• 发现如果能够跳进 \(u\) 子树再跳回 \(u\)，取决于最浅的叶子和 \(u\) 之间的距离是否 \(\leq k\)。

• 记 \(f_u\) 表示以 \(u\) 为根的子树的最大收益， \(g_u\) 表示跳下去之后回到 \(u\) 的最大收益，\({len}_u\) 表示 \(u\) 的最浅叶子到 \(u\) 的距离。

• 对于 \(u\) 来说，如果 \({len}_v+1>k\) 那么就不能跳到 \(v\) 的子树再回来了，此时设置 \(g_v=0\).

• 要选定跳进去后不跳出来的一个子树，这时因为不能考虑 \(g_v\) 的贡献，所以要找一个 \(f_v-g_v\) 最大的子树。

• 总时间复杂度为 \(O(n)\)。

代码

#include<bits/stdc++.h>

using namespace std;

#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)

#define rep(i,a,b) for(int i=a;i<=b;++i)

#define pb push_back

typedef long long LL;

inline int gi(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch))	{if(ch=='-') f=-1;ch=getchar();}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}

	return x*f;

}

template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}

template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}

const int N=1e6 + 7,inf=0x3f3f3f3f;

int n,edc,K;

int head[N],len[N],f[N],g[N];

struct edge {

	int last,to;

	edge() {} edge(int last,int to):last(last),to(to) {}

} e[N*2];

void Add(int a,int b) {

	e[++edc]=edge(head[a],b),head[a]=edc;

	e[++edc]=edge(head[b],a),head[b]=edc;

}

void dfs(int u,int fa) {

	len[u]=inf;

	int fg=1;

	go(u)if(v^fa){

		fg=0;dfs(v,u);

		Min(len[u],len[v]+1);

		if(len[v]+1>K) g[v]=0;

		g[u]+=g[v];

		Max(f[u],f[v]-g[v]);

	}

	if(fg) len[u]=0,g[u]=f[u]=1;

	else f[u]+=g[u];

}

int main() {

	n=gi(),K=gi();

	rep(i,2,n) Add(i,gi());

	dfs(1,0);

	printf("%d\n",f[1]);

	return 0;

}