题意
给定一棵以 (1) 为根的树，你每次可以选择跳到某个叶子节点，再跳到和他深度差不超过 (k) 的祖先。询问最多能够跳到多少个叶子节点。
(n,kleq 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
",f[1]);
return 0;
}