#include #include #include #define LL long long #define Re register int using namespace std; const int N=5e6+3; int n,op,fa[N],pf[N],son[N];LL ans; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline LL get_prufer(){ for(Re i=1;i<=n-1;++i)in(fa[i]),++son[fa[i]]; for(Re i=1,j=1;i<=n-2;++i,++j){ while(son[j])++j;pf[i]=fa[j]; while(i<=n-2&&!--son[pf[i]]&&pf[i]