双 log 做法求卡常

#include<bits/stdc++.h>
//#define int long long
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define constexpr const
using namespace std;
constexpr int N=1e6+5,Inf=N;
__inline void read(int&x){
    char ch=getchar();
    x=0;
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
        x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return;
}
__inline void write(int val){
    if(val>=10)
        write(val/10);
    putchar((val%10)^48);
    return;
}
__inline void writeln(int x){
	write(x);
	putchar('\n');
	return;
}
int n,not0,ct[N],e[N][2],son[N],vis[N],fa[N],dtot,dfn[N],f[N],dtot_ds,dfn_ds[N],top[N],maxv[N*3],tag[N*3],DEP,P,siz[N],son_ds[N],ans;
int dfs_info(int u){
    int maxsiz=0,v;
    siz[u]=1;
    if(e[u][0]){
        v=e[u][0];
        siz[u]+=dfs_info(v);
        if(siz[v]>maxsiz)
            maxsiz=siz[son_ds[u]=v];
        if(e[u][1]){
            v=e[u][1];
            siz[u]+=dfs_info(v);
            if(siz[v]>maxsiz)
                maxsiz=siz[son_ds[u]=v];
        }
    }
    return siz[u];
}
#define get_sib(x) (e[fa[(x)]][e[fa[(x)]][0]==(x)])
void dfs_chain(int u,int tp){
    dfn_ds[u]=(++dtot_ds),top[u]=tp;
    if(son_ds[u]){
        dfs_chain(son_ds[u],tp);
        int sib=get_sib(son_ds[u]);
        if(sib)
            dfs_chain(sib,sib);
        return;
    }
    return;
}
#define max(a,b) (((a)<(b))?(b):(a))
__inline void addseg(int l,int r){
    for(l+=P-1,r+=P+1;l^1^r;){
        l^=1,r^=1;
        (l&1)&&(maxv[l]++,tag[l]++);
        (~r&1)&&(maxv[r]++,tag[r]++);
        maxv[l>>1]=max(maxv[l],maxv[l^1])+tag[l>>1];
        maxv[r>>1]=max(maxv[r],maxv[r^1])+tag[r>>1];
        if(((l>>=1)^(r>>=1))==1)
            break;
        l^=1,r^=1;
        (l&1)&&(maxv[l]++,tag[l]++);
        (~r&1)&&(maxv[r]++,tag[r]++);
        maxv[l>>1]=max(maxv[l],maxv[l^1])+tag[l>>1];
        maxv[r>>1]=max(maxv[r],maxv[r^1])+tag[r>>1];
        if(((l>>=1)^(r>>=1))==1)
            break;
    }
    for(l>>=1;l;){
        maxv[l]=max(maxv[l<<1],maxv[l<<1|1])+tag[l],l>>=1;
        maxv[l]=max(maxv[l<<1],maxv[l<<1|1])+tag[l],l>>=1;
        maxv[l]=max(maxv[l<<1],maxv[l<<1|1])+tag[l],l>>=1;
        maxv[l]=max(maxv[l<<1],maxv[l<<1|1])+tag[l],l>>=1;
    }
    return;
}
__inline void modify(int x,int k){
    x+=P;
    for(int y=x;y;)
        k-=tag[y>>=1],
        k-=tag[y>>=1],
        k-=tag[y>>=1],
        k-=tag[y>>=1];
    maxv[x]=k;
    for(x>>=1;x;){
        maxv[x]=max(maxv[x<<1],maxv[x<<1|1])+tag[x],x>>=1;
        maxv[x]=max(maxv[x<<1],maxv[x<<1|1])+tag[x],x>>=1;
        maxv[x]=max(maxv[x<<1],maxv[x<<1|1])+tag[x],x>>=1;
        maxv[x]=max(maxv[x<<1],maxv[x<<1|1])+tag[x],x>>=1;
    }
    return;
}
__inline void modifyp(int x,int val){
    return modify(dfn_ds[x],val);
}
__inline void addchain(int x){
    while(x){
        addseg(dfn_ds[top[x]],dfn_ds[x]);
        x=fa[top[x]];
    }
    return;
}
#undef max
__inline void add(int x){
    #define lowbit(x) ((x)&(-(x)))
    for(;x<=n;x+=lowbit(x))
        f[x]++;
    return;
    #undef lowbit
}
__inline int qry(int x){
    #define lowbit(x) ((x)&(-(x)))
    int ret=0;
    for(;x;x-=lowbit(x))
        ret+=f[x];
    return ret;
    #undef lowbit
}
__inline int qry(int l,int r){
    if(l>r)
        return 0;
    else
        return qry(r)-qry(l-1);
}
void dfs(int u){
    dfn[u]=(++dtot);
    if(e[u][0]){
        dfs(e[u][0]);
        if(e[u][1])
            dfs(e[u][1]);
    }
    return;
}
int st=clock();
signed main(){
    read(n);
    n++;
    for(int i=2,mother;i<=n;i++){
        read(mother);
        if(!son[mother]){
            fa[i]=mother;
            e[fa[i]][ct[fa[i]]]=i;
            vis[i]=1,ct[fa[i]]=1;
        }
        else{
            fa[i]=son[mother];
            if(!not0)[[unlikely]]
                not0=i;
        }
        son[mother]=i;
    }
    for(int i=2;i<=n;i++)
        if(!vis[i])
            e[fa[i]][ct[fa[i]]]=i,ct[fa[i]]=1;
    if(!not0)
        not0=Inf;
    dfs(1);
    dfs_info(1),dfs_chain(1,1);
    DEP=__lg(n)+1,P=1<<DEP;
    add(dfn[1]);
    dfn[0]=Inf;
    for(int i=2,sib;i<=n;i++){
        add(dfn[i]);
        sib=get_sib(i);
        if(dfn[sib]<dfn[i])
            modifyp(sib,qry(dfn[fa[i]]+1,dfn[i]-1)+Inf);
        else
            ans=max(ans,qry(dfn[fa[i]]+1,dfn[i]-1));
        addchain(i);
        writeln(max(ans,maxv[1]-Inf)+(not0<=i));/*
        if(i>800000&&1.0*(clock()-st)/CLOCKS_PER_SEC>0.99)[[unlikely]]
            return 0;*/
    }
    return 0;
}