首先发现一个性质，那就是每个点的点权是 \(\log n\) 级别的。因为假设要造出一个点权为 \(i\) 的点至少需要大小为 \(mn_i\) 的子树，那么显然有 \(mn_i=\sum\limits_{j=0}^{i-1}mn_j+1\)，即 \(mn_i=2^i\)。
由于点权不是很大，因此我们很容易地往变换复合的角度思考。将整棵树进行轻重链剖分，然后对于每个点维护一个变换 \(p_i\)，表示如果重儿子点权为 \(i\)，那么这个点的点权就会变成 \(p_i\)，这样查询单点点权就直接将重链底部到当前点上的变换进行一遍复合即可，用线段树维护，类似于 DDP。计算点权和的话就额外在线段树上每个节点上记录一下 \(sum_i\) 表示如果初始值为 \(i\) 那么经过这些变换复合后得到的所有时刻的值之和是多少。
有不少细节需要考虑，比方说没有加入的点的变换设成什么。
const int MAXN=3e5;
int n,fa[MAXN+5],hd[MAXN+5],to[MAXN+5],nxt[MAXN+5],ec;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int siz[MAXN+5],wson[MAXN+5],cnt[MAXN+5][25],bot[MAXN+5];
int top[MAXN+5],dfn[MAXN+5],rid[MAXN+5],tim;
ll res=0;
void dfs1(int x){
siz[x]=1;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];dfs1(y);siz[x]+=siz[y];
if(siz[y]>siz[wson[x]])wson[x]=y;
}
}
void dfs2(int x,int tp){
top[x]=tp;rid[dfn[x]=++tim]=x;if(wson[x])dfs2(wson[x],tp);
for(int e=hd[x];e;e=nxt[e])if(to[e]!=wson[x])dfs2(to[e],to[e]);
}
struct dat{
int p[25],sum[25];
dat(){memset(p,0,sizeof(p));memset(sum,0,sizeof(sum));}
friend dat operator +(const dat &X,const dat &Y){
dat res;
for(int i=0;i<=21;i++)res.p[i]=Y.p[X.p[i]],res.sum[i]=X.sum[i]+Y.sum[X.p[i]];
return res;
}
}A,B;
struct node{int l,r;dat v;}s[MAXN*4+5];
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;s[k].v=A;if(l==r)return;
int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void modify(int k,int p,dat v){
if(s[k].l==s[k].r)return s[k].v=v,void();
int mid=s[k].l+s[k].r>>1;
if(p<=mid)modify(k<<1,p,v);else modify(k<<1|1,p,v);
s[k].v=s[k<<1|1].v+s[k<<1].v;
}
pii query(int k,int l,int r,int x){
if(l<=s[k].l&&s[k].r<=r)return mp(s[k].v.p[x],s[k].v.sum[x]);
int mid=s[k].l+s[k].r>>1;
if(r<=mid)return query(k<<1,l,r,x);
else if(l>mid)return query(k<<1|1,l,r,x);
else{
pii p1=query(k<<1|1,mid+1,r,x),p2=query(k<<1,l,mid,p1.fi);
return mp(p2.fi,p1.se+p2.se);
}
}
int ask_sum(int x,int y){
int sum=query(1,dfn[y],dfn[bot[y]],21).se;
if(wson[x])sum-=query(1,dfn[wson[x]],dfn[bot[wson[x]]],21).se;
return sum;
}
int ask_val(int x){return query(1,dfn[x],dfn[bot[x]],21).fi;}
pii cur[MAXN+5];
void upd(int x){
dat d;int fs=-1,sc=-1;
for(int i=0;i<=21;i++)if(!cnt[x][i]){if(!~fs)fs=i;else if(!~sc)sc=i;}
for(int i=0;i<=21;i++)d.sum[i]=d.p[i]=(i==fs)?sc:fs;
if(mp(sc,fs)!=cur[x])cur[x]=mp(sc,fs),modify(1,dfn[x],d);
}
int main(){
scanf("%d",&n);++n;
for(int i=0;i<=21;i++)A.p[i]=21;
for(int i=2;i<=n;i++)scanf("%d",&fa[i]),adde(fa[i],i);
dfs1(1);dfs2(1,1);build(1,1,n);
modify(1,dfn[1],B);
for(int i=1;i<=n;i++)if(top[i]==i){
int cur=i;
while(wson[cur])cur=wson[cur];
bot[i]=cur;
}
for(int i=1;i<=n;i++)if(!bot[i])bot[i]=bot[top[i]];
for(int i=2;i<=n;i++){
int x=fa[i];
while(x){
res-=ask_sum(x,top[x]);
if(fa[top[x]])cnt[fa[top[x]]][ask_val(top[x])]--;
x=fa[top[x]];
}
if(wson[fa[i]]!=i)cnt[fa[i]][0]++;x=fa[i];modify(1,dfn[i],B);
while(x){
upd(x);res+=ask_sum(x,top[x]);
if(fa[top[x]])cnt[fa[top[x]]][ask_val(top[x])]++;
x=fa[top[x]];
}
print(res,'\n');
}print_final();
return 0;
}