这道题目是Claris推荐给我的，那个时候，google突然能够上了，Claris就搜到了一个波兰人的blog，里面有关于这道题目的结论，结论是:[tex]ans=\max(i+\lceil\frac{sum[i]}{k} \rceil)[/tex]，其中，i是指第i层（深度为i），sum[i]是指深度大于i的结点的个数。

那个波兰人的blog里面有证明，不过证明是图片格式的，学校网速差不能看，后来google上不去了，就更不能看了。Claris自己没有办法证明，但还是根据这个规律AC了这道题目。这一次WC，和我同寝室的zhw大神正好也AC了这道题目，然后Claris就怂恿我去问zhw大神这道题，zhw大神的做法是一样的，不过他给出了简略证明，其中有一句话极其重要：“当第i层之后，每一次都能取k个结点，那么这个式子就成立了。而符合这样要求的一层肯定是存在的。”

因为BZOJ挂了，这道题目暂时看不到，不过可以去Main上看英文版本的，题目大意就是，有一棵一百万结点的树，每一次可以查询k个结点，一个结点可以被查询，当且仅当其父结点被查询了，那么第一次只能查询根结点。现在，询问对于一个k，最少需要查询对少次才能将所有结点都查询一遍。

我们首先里证明后面半句：这样的一层必然是存在的。首先，如果总层数为h，每一层的结点都小于k，那么我们就需要查询h次，符合要求的那一层（我将其命名为关键层）就是h层。

那如果有一层（假设为第x层）的结点个数大于k，我们该怎么做？首先，当然是查询这一层的k个结点，至于剩下的结点，我们就不用管它，我们下一次查询的时候，继续查询下一层，如果下一层的结点个数大于k，我们也只查询其中的k个结点，否则，我们查询了这一层的t个结点之后，在第x层找到x-t个未被查询的结点查询，接下来就只有两种情况：1、每次都可以查询一层，且从某一层（比如说上面说的x层）将不足的结点查询完，那么x-1层就是关键层，我们的公式自然成立。2、从第y+1层开始，多余的结点查询完了，每一层的节点个数再次不足k个，很明显，这个时候我们就正好查询了y次，x和y都不是关键层，但是没有关系，如果接下来都是这样的话，第h层就是关键层。

实际情况自然要更加复杂，但是都离不开这两种情况。所以，我们必然能够找到一个关键层使得我们找到的结论成立。

那么，为什么要求max且对每一层都用这个公式求一下？我们发现，如果一层并不是关键层，但是我们把其当作关键层来看，也就是说，接下来每一次都可以查询k个结点，但实际上，我们接下来不可能每次都查询k个结点，这样的话，理论的查询次数小于等于实际的查询次数，所以，必然小于最后的答案，至于max，这是显然的。因为我们可以发现，关键层有且仅有一层，其他层用这个公式求出来的答案必然小于关键层求出的答案。

以上就是关于这个结论的证明，剩下的就是程序实现了。

但是在程序实现的过程中还是有一些问题，因为这题需要进行一百万次查询，如果每次我们都查询这么多层的话，肯定是会超时的，毕竟深度最多可能有一百万。但是，我们先忽略向上取整和k的值，整个式子就可以转化成斜率的式子了，用队列存下可能成为解的情况，之后再从小到大依次枚举k，最多枚举到n，因为k可能是很大的数，而且，当k>n之后，答案就是整棵树的深度了。这样做的复杂度明显是O(1)的。

//ans=max(i+sum[i]/k)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1000100;
int n,m,p[N];
int fa[N],f[N],d[N],ans[N];
int st[N],L,R,deep=1;
bool ok(int i,int j,int k) { return (ll)(f[k]-f[j])*(i-j)>=(ll)(f[j]-f[i])*(j-k);}
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
int main() {
    int i,j;
    read(n); read(m); f[d[1]=0]=deep=1;
    for (i=1;i<=m;i++) read(p[i]);
    for (i=2;i<=n;i++) {
        read(fa[i]);
        d[i]=d[fa[i]]+1; f[d[i]]++;
        if (d[i]>=deep) deep=d[i]+1;
    }
    for (i=deep;~i;i--) f[i]=f[i]+f[i+1];
    for (i=deep;~i;i--) {
        while (R>1&&ok(st[R-1],st[R],i)) R--;
        st[++R]=i;
    }
    for (L=1,i=n;i;i--) {
        while (L<R&&(ll)i*(st[L]-st[L+1])<=f[st[L+1]]-f[st[L]]) L++;
        if (f[st[L]]%i==0) ans[i]=st[L]+f[st[L]]/i;
        else ans[i]=st[L]+f[st[L]]/i+1;
    }
    for (i=1;i<m;i++) if (p[i]>n) printf("%d ",deep);
    else printf("%d ",ans[p[i]]);
    if (p[i]>n) printf("%d\n",deep);
    else printf("%d\n",ans[p[i]]);
    return 0;
}