有一个贪心的直觉：最优方案形如前 $x$ 层 $x$ 步删完，后面每次删 $k$ 个。证明太复杂，这不是这篇文章的重点。

于是预处理出 $c_i$ 表示深度大于 $i$ 的节点个数，那么答案为 $\max\limits_{i}\{i+\left\lceil\frac{c_i}{k}\right\rceil\}$，变形得到 $\max\limits_{i}\{\left\lceil\frac{c_i+ki}{k}\right\rceil\}$。

于是转化为求 $f_k=c_i+ki$ 的最大值。观察到这个式子就是斜率优化的形式（$b=y-tx$，其中截距 $b=f_k$ 是待求答案，斜率 $t=-k$ 是定值，$x$ 和 $y$ 都只与 $i$ 有关）。这里我们细讲一下斜率优化。

我们把所有 $(x,y)$ 的可能值 $(i,c_i)$ 看作平面上的点，我们要求的就是对于一条斜率为 $-k$ 且穿过至少一个点的直线，它的截距 $b$ 最大是多少。

我们考虑拿一条斜率为 $-k$ 的直线从平面的右上角扫下来，容易发现，它第一个碰到平面上的点时，此时的 $b$ 一定是最大的。这样做复杂度很高，但手模一下我们发现，很多点是永远不会被用到的，具体来说，只有"最外面一层"的点才有用。

研究一下这些点的性质，显然它们形成了一个上凸壳（的右半部分），满足对于任意 $i$，$i$ 和 $i-1$ 组成直线的斜率大于 $i$ 和 $i+1$ 的斜率（因为斜率都是负数）。这个凸壳可以简单维护，我们使用一个队列，每次想要把一个点加入凸壳时，我们判断队列最后两个点加上它之后是否满足上面斜率的性质，不满足则弹出队尾。直到条件满足，把这个点加入即可。

于是我们现在就是拿一根直线去切凸壳。考虑人为给 $k$ 离线排序，那么每次直线斜率减小，只会"越来越斜"，显然切到的点也会有单调性。于是依次处理询问，每次找切点，答案就是这根直线切到这个点时的截距。

AC code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+5;
int n,m,q[N],de[N],l=1;
int s[N],mx,an[N],r;
struct A{
	int x,y;
	bool operator<(const A&x)const{return y<x.y;}
}a[N];
double sl(int x,int y){
	if(x==y)return -1e9;
	return (s[x+1]-s[y+1])*1.0/(x-y);
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m,s[1]=de[1]=1;
	for(int i=1;i<=m;i++)
		cin>>a[i].y,a[i].x=i;
	sort(a+1,a+m+1);
	for(int i=2,x;i<=n;i++){
		cin>>x,de[i]=de[x]+1;
		mx=max(mx,de[i]),s[de[i]]++;
	}
	for(int i=mx;i>0;i--)s[i]+=s[i+1];
	for(int i=1;i<=mx;i++){
		while(l<=r&&sl(i,q[r])>=sl(q[r],q[r-1]))r--;
		q[++r]=i;
	}
	for(int i=1;i<=m;i++){
		while(l<r&&-a[i].y<sl(q[l],q[l+1]))l++;
		an[a[i].x]=q[l]+ceil(s[q[l]+1]*1.0/a[i].y);
	}
	for(int i=1;i<=m;i++)cout<<an[i]<<" ";
	return 0;
}