思路源于某巨佬：巨佬博客
对于 1<=k<=n 答案最大是n-1 最小是0 于是我们从大到小枚举答案（这样的话小的值会覆盖大的值） 然后看这个答案对应的最小k是多少 最后在做一遍前缀最小值就行了
找ans对应最小k的过程肯定是贪心的 我们找到深度最大的点 向上走ans步（找ans级祖先） 然后把它的子树都标记就可以了
当最大的深度<=nowans时 退出循环
当ans 确定的时候 最多进行 n/(ans+1) 次操作 每次操作复杂度是 logn级别的
所以 总复杂度 是 nlogn^2 （调和级数求和是logn级别的）
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
vector<int>g[N],st;
int tot,in[N],out[N],n,ans[N],rnk[N];
int fa[N][22],dep[N];
typedef long long ll;
void init(){tot=0;for(int i = 1; i <= n; i++) g[i].clear(),ans[i]=n-1;
}
void dfs(int u,int f){rnk[in[u]=++tot]=u;dep[u]=dep[f]+1;fa[u][0]=f;for(int i = 1; i <= 19; i++) fa[u][i]=fa[fa[u][i-1]][i-1];for(auto v:g[u]){if(v==f) continue;dfs(v,u);}out[u]=tot;
}
int kth(int u,int k){int bit=0;while(k){if(k&1) u=fa[u][bit];k>>=1;bit++;}return u;
}
struct segTree{int nd,mx;bool cov;
}T[N<<2];
#define ls id<<1
#define rs ls|1
#define mid (l+r>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
void pushup(int id){T[id].mx=0;if(!T[ls].cov&&T[ls].mx>T[id].mx) T[id]=T[ls];if(!T[rs].cov&&T[rs].mx>T[id].mx) T[id]=T[rs];
}
void update(int id,int l,int r,int L,int R,int v){if(L<=l&&R>=r){T[id].cov=v;return;} if(L<=mid) update(lson,L,R,v);if(R>mid) update(rson,L,R,v);pushup(id);
}
void build(int id,int l,int r){T[id].cov=false;if(l==r){T[id].mx=dep[T[id].nd=rnk[l]];return;}build(lson);build(rson);pushup(id);
}
int main(){while(~scanf("%d",&n)){init();for(int i = 2; i <= n; i++){int x;scanf("%d",&x);g[i].push_back(x);g[x].push_back(i);}dep[0]=-1;dfs(1,0);build(1,1,n);for(int nowans=n-1; nowans >= 0; nowans--){int ndcos=0;st.clear();while(1){ndcos++;if(T[1].mx<=nowans) break;int u = T[1].nd;u = kth(u,nowans);update(1,1,n,in[u],out[u],1);st.push_back(u);} ans[ndcos]=nowans;for(auto v:st) update(1,1,n,in[v],out[v],0);}for(int i = 2; i <= n; i++) ans[i]=min(ans[i],ans[i-1]);ll sum=0;for(int i = 1; i <= n; i++) sum+=ans[i];printf("%lld\n",sum);}return 0;
}