题目描述
有一棵不断加叶子的树，叶子的权值是0，其余节点的权值是其子节点的\(\texttt{mex}\)
- \(\texttt{mex}\)定义为最小的没有出现过的自然数。
解题思路
首先离线建树，把树做轻重链剖分。
对于一个节点\(u\)，设其轻儿子中最小的没有出现能过的自然数是\(A\)，次小的是\(B\)，其重儿子权值是\(x\)。
-
若\(x=A\)，则\(v(u)=B\)
-
若\(x\neq A\)，则\(v(u)=A\)
我们可以用一个五元组\((v,A,B,X,Y)\)来描述这样的信息：
-
若\(x=v\)，则返回的是\(A\)，权值和会加上\(X\)。
-
若\(x\neq v\)，则返回的是\(B\)，权值和会加上 \(Y\)。
观察到这样的信息是可以合并的，因此我们用线段树维护一条重链的信息。
修改和普通动态\(dp\)的修改是类似的
有一个小细节是一个点的权值是\(O(\log n)\)的，因此可以用数组存储每个点轻子树的点权，方便求出\(A,B\)。
复杂度\(O(nlog^2n)\)
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+7;
typedef long long LL;
struct Info
{
int x;
int A1,A2;
LL S1,S2;
Info(){x=A1=A2=S1=S2=-1;}
Info(int a,int b,LL c,int d,LL e){x=a;A1=b;S1=c;A2=d;S2=e;}
};
inline void process(int &v,LL &w,Info U)
{
if(v==U.x)
{
v=U.A1;
w+=U.S1;
}
else
{
v=U.A2;
w+=U.S2;
}
}
Info Push(Info A,Info B)
{
if(A.x==-1)return B;
Info C;
C.x=A.x;
int v;LL w;
v=A.A1,w=A.S1;process(v,w,B);C.A1=v;C.S1=w;
v=A.A2;w=A.S2;process(v,w,B);C.A2=v;C.S2=w;
return C;
}
int n;
struct edge
{
int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{
e[++t].y=y;
e[t].next=link[x];
link[x]=t;
}
int siz[N],top[N],son[N],dfn[N],timer=0;
int fa[N],st[N],ed[N];
void dfs(int x,int pre)
{
siz[x]=1;fa[x]=pre;
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(y==pre)continue;
dfs(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])son[x]=y;
}
}
void Exdfs(int x,int topth)
{
top[x]=topth;
dfn[x]=++timer;
if(x==topth) st[x]=dfn[x];
ed[top[x]]=dfn[x];
// cout<<x<<' '<<topth<<' '<<st[topth]<<' '<<ed[topth]<<endl;
if(!son[x])return;
Exdfs(son[x],topth);
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(y==fa[x]||y==son[x])continue;
Exdfs(y,y);
}
}
Info tr[N*4];
void update(int k,int l,int r,int x,Info U)
{
// cout<<"update:"<<x<<endl;
if(l==r)
{
tr[k]=U;
// cout<<l<<' '<<r<<' '<<tr[k].x<<' '<<tr[k].A1<<' '<<tr[k].A2<<' '<<tr[k].S1<<' '<<tr[k].S2<<endl;
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(k<<1,l,mid,x,U);
else update(k<<1|1,mid+1,r,x,U);
tr[k]=Push(tr[k<<1|1],tr[k<<1]);
// cout<<l<<' '<<r<<' '<<tr[k].x<<' '<<tr[k].A1<<' '<<tr[k].A2<<' '<<tr[k].S1<<' '<<tr[k].S2<<endl;
}
Info query(int k,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return tr[k];
int mid=(l+r)>>1;
if(R<=mid)return query(k<<1,l,mid,L,R);
if(L>mid) return query(k<<1|1,mid+1,r,L,R);
return Push(query(k<<1|1,mid+1,r,mid+1,R),query(k<<1,l,mid,L,mid));
}
int w[N];
int B[N][30];
LL sum=0;
inline void guess(int x,int &u,int &v)
{
// cout<<u<<' '<<v<<' '<<B[x][0]<<endl;
for(int i=0;i<=29;i++)
if(!B[x][i])
{
if(u==-1) u=i;
else if(v==-1) v=i;
}
}
void modify(int x)
{
int p=top[fa[x]];
while(p)
{
Info U=query(1,1,n+1,st[p],ed[p]);
sum-=U.S2;
p=top[fa[p]];
}
//w[x]=0;
update(1,1,n+1,dfn[x],Info(0,1,1,0,0));
p=top[x];
// cout<<x<<':'<<dfn[x]<<endl;
//cout<<query(1,1,n,st[1],ed[1]).S2<<endl;
while(p)
{
// cout<<query(1,1,n,st[1],ed[1]).S2<<endl;
// cout<<"modify:"<<p<<' '<<w[p]<<' '<<st[p]<<' '<<ed[p]<<' '<<sum<<endl;
Info U=query(1,1,n+1,st[p],ed[p]);
sum+=U.S2;
if(!fa[p])break;
if(w[p]>=0) B[fa[p]][w[p]]--;
w[p]=U.A2;
if(w[p]>=0) B[fa[p]][w[p]]++;
int u=-1,v=-1;
guess(fa[p],u,v);
// cout<<"guess:"<<u<<' '<<v<<endl;
update(1,1,n+1,dfn[fa[p]],Info(u,v,v,u,u));
p=top[fa[p]];
}
// if(x==3)exit(0);
}
int cr[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&cr[i]);
add(cr[i],i+1);
}
for(int i=1;i<=n+1;i++)w[i]=-1;
dfs(1,0);Exdfs(1,1);
modify(1);
for(int i=1;i<=n;i++)
{
modify(i+1);
printf("%lld\n",sum);
}
return 0;
}