直接扫一遍,统计即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
// char buf[1<<21],*p1=buf,*p2=buf;
// #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); }
while(isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
int n,a[MAXN];
int dep[MAXN<<2];
int main()
{
n=read();
dep[1]=0;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++)
{
dep[i*2]=dep[i*2+1]=dep[a[i]]+1;
}
for(int i=1;i<=n*2+1;i++) printf("%d\n",dep[i]);
return 0;
}