首先有一个结论，树中存在一个深度 \(dep\)，使得深度小于等于 \(dep\) 的点只需 \(dep\) 次覆盖完，而大于 \(dep\) 的除最后一次外其他每次都可以填充 \(k\) 次。
证明：在 \(dep\) 上面的所有点如果不能连续填充 \(k\) 次，说明均摊下来每一层的点数肯定小于 \(k\)，这样的话一定存在上面的只用取 \(dep\) 次的深度，那下面层数均摊大于 \(k\)，所以每次能填满 \(k\) 次，所以就是在找一个层数均摊为 \(k\) 的分界点，那么这种层数一定存在。
层数均摊什么意思呢，就是如果一层的节点大于了 \(k\)，我们就将多余的节点放到下一个一层不足 \(k\) 个的深度上去。
现在我们就是对于每一个 \(k\)，找到这个深度即可。
假设 \(i\) 是这个分界点，那么对于其他的深度，答案一定是小于等于它的。
证明上述：若深度小于 \(i\)，那么会多包含能填满 \(k\) 的深度，那么就会多选节点，如果深度大于 \(i\)，那么层度均摊大于 \(k\) 的一层会被一次选完，明显这两种情况都更优。
那么我们就可以列出式子，设 \(sum_i\) 为在 \(i\) 层及以下的节点个数。
那么 \(i+\left\lceil\frac{sum_i}{k}\right\rceil\ge j+\left\lceil\frac{sum_j}{k}\right\rceil\)。
相当于我们要求一个 \(i\) 使得 \(i+\left\lceil\frac{sum_i}{k}\right\rceil\) 最大。
设答案为 \(ans\)，那么：
\[\begin{aligned} \\ans&=i+\left\lceil\frac{sum_i}{k}\right\rceil \\k\times ans&=k\times i+sum_i \\-sum_i&=k\times i-k\times ans \end{aligned}\]上面明显是个斜率式子，考虑维护凸包，由于要求最大值，而截距越大答案越小，所以考虑维护下凸包。
那么每一个点即为 \((i,sum_{i+1})\)。
维护凸包后，对于询问，按 \(k\) 递减排序，用单调队列去找凸包上的点即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define pii pair<int,int>
using namespace std;
const int N=1e6+5;
int n,m,q[N],dep[N],sum[N],maxn,ans[N];
pii a[N];
int cmp(pii x,pii y)
{
return x.second<y.second;
}
inline double slope(int x,int y)
{
if(x==y)return 1e9;
return (-sum[x+1]+sum[y+1])*1.0/1.0/(x-y);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d",&a[i].second),a[i].first=i;
sort(a+1,a+1+m,cmp);
sum[1]=dep[1]=1;
for(int i=2;i<=n;i++)
{
int x;
scanf("%d",&x);
dep[i]=dep[x]+1;
maxn=max(maxn,dep[i]);
sum[dep[i]]++;
}
for(int i=maxn;i>0;i--)sum[i]+=sum[i+1];
int l=1,r=1;
for(int i=1;i<=maxn;i++)
{
while(l<r&&slope(q[r],q[r-1])>=slope(i,q[r]))r--;
q[++r]=i;
}
for(int i=1;i<=m;i++)
{
while(l<r&&slope(q[l],q[l+1])<a[i].second)l++;
ans[a[i].first]=q[l]+(sum[q[l]+1]+a[i].second-1)/a[i].second;
}
for(int i=1;i<=m;i++)printf("%d ",ans[i]);
return 0;
}
/*
20 3
2 3 1
1 1 1 3 4 3 2 8 6 9 10 12 12 13 14 11 11 11 11
*/