来自FallDream的博客，未经允许，请勿转载，谢谢。
看完题目，一般人都能想到 容斥稳了 。这样我们只要统计有多少点对满足gcd是i的倍数。
考虑长链剖分，每次合并的时候，假设我已经求出轻儿子子树内每一个距离的点的数量，我们需要先对这个序列做一个变换，把每个数变成下标是它倍数的数的和。
然后枚举轻儿子到这个点距离dis，这样答案加上现在这棵树内已经计算的部分中 到这个点的距离是dis的倍数的数的和。
考虑分块，对于dis>=k的，暴力做。对于dis<=k的，我们顺便维护数组f[i][j],表示深度膜i等于j的数的数量。
长链剖分的合并次数是O(n)的，所以这个算法的复杂度是根号级别的。
然后玄学调参 我一路调着把块大小从根号那里调到了十几那里巨快 什么鬼 应该是数据问题吧
#include<iostream>
#include<cstdio>
#define MN 200000
#define MK 14
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct edge{int to,next;}e[MN+];long long ans[MN+];
int n,head[MN+],cnt=,num[MK+][MK+],fa[MN+],dep[MN+],D[MN+],mxdp[MN+],mx[MN+],s[MN+],S[MN+],*mem[MN+];
inline void ins(int f,int t){e[++cnt]=(edge){t,head[f]};head[f]=cnt;}
void Pre(int x)
{
mxdp[x]=dep[x];mx[x]=;
for(int i=head[x];i;i=e[i].next)
{
Pre(e[i].to);
if(mxdp[e[i].to]>mxdp[x]) mxdp[x]=mxdp[e[i].to],mx[x]=e[i].to;
}
}
void Solve(int x,int flag)
{
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=mx[x]) Solve(e[i].to,);
if(mx[x]) Solve(mx[x],);
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=mx[x])
{
for(int j=dep[e[i].to];j<=mxdp[e[i].to];++j) S[j-dep[e[i].to]+]=mem[e[i].to][j-dep[e[i].to]];
int len=mxdp[e[i].to]-dep[e[i].to]+;
for(int ii=;ii<=len;++ii)
for(int j=ii<<;j<=len;j+=ii) S[ii]+=S[j];
for(int j=;j<=len;++j)
if(j<=MK) ans[j]+=1LL*S[j]*num[j][dep[x]%j];
else for(int k=j;k<=mxdp[x]-dep[x];k+=j) ans[j]+=1LL*S[j]*s[dep[x]+k];
for(int j=dep[e[i].to];j<=mxdp[e[i].to];++j)
{
s[j]+=mem[e[i].to][j-dep[e[i].to]];
for(int k=;k<=MK;++k) num[k][j%k]+=mem[e[i].to][j-dep[e[i].to]];
}
}
++s[dep[x]];for(int j=;j<=MK;++j) ++num[j][dep[x]%j];
if(!flag)
{
mem[x]=new int[mxdp[x]-dep[x]+];
for(int j=dep[x];j<=mxdp[x];++j)
{
mem[x][j-dep[x]]=s[j],s[j]=;
for(int k=;k<=MK;++k) num[k][j%k]=;
}
}
} int main()
{
n=read();
for(int i=;i<=n;++i) ins(fa[i]=read(),i),++D[dep[i]=dep[fa[i]]+];
Pre();Solve(,);
for(int i=n;i;D[i]+=D[i+],--i)
for(int j=i<<;j<=n;j+=i)
ans[i]-=ans[j];
for(int i=;i<n;++i) printf("%lld\n",ans[i]+D[i]);
return ;
}