CF1740H MEX Tree Manipulation

题目描述

有一棵不断加叶子的树，叶子的权值是0，其余节点的权值是其子节点的$\text{mex}$

• $\text{mex}$定义为最小的没有出现过的自然数。

解题思路

首先离线建树，把树做轻重链剖分。

对于一个节点$u$，设其轻儿子中最小的没有出现能过的自然数是$A$，次小的是$B$，其重儿子权值是$x$。

• 若$x=A$，则$v(u)=B$

• 若$x\ne A$，则$v(u)=A$

我们可以用一个五元组$(v,A,B,X,Y)$来描述这样的信息：

• 若$x=v$，则返回的是$A$，权值和会加上$X$。

• 若$x\ne v$，则返回的是$B$，权值和会加上 $Y$。

观察到这样的信息是可以合并的，因此我们用线段树维护一条重链的信息。

修改和普通动态$dp$的修改是类似的

有一个小细节是一个点的权值是$O(\log n)$的，因此可以用数组存储每个点轻子树的点权，方便求出$A,B$。

复杂度$O(nlo{g}^{2}n)$

#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;
}