这道题其实很简单,求k个到根的链,使得链上的节点的个数尽可能多,如果节点被计算过了,就不能再被计算了,其实我们发现,只要k>=叶子节点,那么肯定是全部,所以我们考虑所有的叶子节点,DFS到根节点后,往上递归,我们能比较容易的求出某个节点,所有儿子节点的最深深度,那么对于上面一个节点,其实只有一个最长那个影响,所有我们可以保存每个节点的最深深度,然后往上递归,递归到某个节点的时候,查询所有子树的最深深度,把这个最深深度+1当场当前节点的最深深度,其他节点实际上已经变成链了,那么我们用优先队列保存所有的链,也就是对应链的长度,然后找出前k大的链,求和即可,这样就不会重复了。
#include<bits/stdc++.h>
using namespace std;
const int maxx = 2e5+;
int ver[maxx],edge[maxx],head[maxx],Next[maxx];
int n,k,tot;
priority_queue<int>q;
int d[maxx];
void add(int x,int y){
ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
ver[++tot]=x;Next[tot]=head[y];head[y]=tot;
}
int dfs(int u,int fa){
d[u]=;
priority_queue<int>s;
s.push(d[u]);
for (int i=head[u];i;i=Next[i]){
int v=ver[i];
if (v==fa)continue;
dfs(v,u);
s.push(d[v]+);
}
d[u]=s.top();
s.pop();
while(s.size()){
q.push(s.top()-);
s.pop();
}
}
int main(){
while(~scanf("%d%d",&n,&k)){
for (int i=;i<=n;i++){
int tmp;
scanf("%d",&tmp);
add(i,tmp);
}
dfs(,);
q.push(d[]);
int sz=q.size();
int ans=;
for (int i=;i<=min(sz,k);i++){
ans+=q.top();
q.pop();
}
printf("%d\n",ans);
}
return ;
}