想象一下(imagine)

题目描述

 

我们高大的老班举起了有半个他那么高的三角板，说：“你们想象一下——”

于是你就陷入了想象……

有一棵n个点的树，每个叶子节点上都有一个人，他们按照每秒钟走一条边的速度向树根（节点1）前进。

你可以运用k次想象之力，让某一个节点（除了根节点）上的所有人瞬间（耗时为0）转移到这个节点的父亲上。

你想知道最少需要多少时间，所有人可以到达根节点。

 

 

输入

 

输入的第一行包含两个整数n,k，含义见问题描述。

接下来n-1行，第i行一个整数fai，表示节点i的父亲为fai。

 

 

输出

 

输出一行一个整数，表示所有人到达根节点最少需要的时间。

 

 

样例输入

【样例1输入】6 212224【样例2输入】3 212

样例输出

【样例1输出】1【样例2输出】0

提示

 

 

 

【样例1说明】

一开始，在节点3,5,6上分别有一个人，我们称他们为A,B,C。

时刻0，在节点6运用想象之力，A到达节点4。

第1秒，A,B,C走到节点2。

时刻1，在节点2运用想象之力，A,B,C到达节点1，即目的地。

共用时1秒。

 

【样例2说明】

一开始只有节点3上有一个人。

时刻0，在节点3运用想象之力，这个人到达节点2；

此时仍然为时刻0，在节点2运用想象之力，这个人到达节点1。

【子任务】

测试点	n	k	特殊性质
1	≤8	<n	无
2~4	≤100
5~8	≤3000
9	≤500000	=1
10		<n	树是一条链
11~20			无

 

---

solution

考场时的想法：答案是有单调性的，那我二分一个mid，然后把所有点往上跳mid步

在用树形dp看看是否合法

效率O(nlog2) 90分

然而这题有O（n）做法

贪心把所有叶子往上跳，如果剩下的边不足k条，就break

因为想象应该越晚用越好（一次拉多个）

好吧说实话我也不太会证

1.一个节点最多只会使用1次想象之力（当最后一个人经过它的时候）2.对于一个人来说，对他用的想象之力一定越靠近根越好（尽可能多的与其它点共用）。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define maxn 500005using namespace std;int n,K,f[maxn],flag[maxn],s[maxn],ans;struct node{ int x,bs;};queue
           
            q;int main(){ cin>>n>>K; for(int i=2;i<=n;i++){ scanf("%d",&f[i]); s[f[i]]++; } for(int i=1;i<=n;i++)if(!s[i])q.push(node{i,0}); int sum=n-1;if(K==sum){puts("0");return 0;} while(!q.empty()){ node a=q.front();q.pop(); sum--;if(sum<=K){ans=a.bs+1;break;} s[f[a.x]]--; if(!s[f[a.x]]){ node ne;ne.x=f[a.x];ne.bs=a.bs+1; q.push(ne); } } cout<
            
             <