CF1740H MEX Tree Manipulation

题面传送门

首先肯定要先离线下来把树建好然后一个一个点加进去。

先来考虑单个点答案的上届，设\(g_i\)表示mex为\(i\)的点子树内至少几个点，容易发现是\(g_i=2^i\)，那么单个点的答案就是\(O(\log n)\)的。然后你还可以进一步推出来整棵树的答案是\(O(n)\)级别的但是没有什么用。

考虑轻重链剖分以后ddp，每个点维护一个函数表示\(f(x)\)表示重儿子的权值是\(x\)的情况下当前点的权值是什么以及权值和是多少，容易发现我们要做的其实就是对一条重链上的函数进行复合，也即求\(f_1(f_2(f_3(\dots)))\)。

因为这个函数值域是\(O(\log n)\)的所以可以直接暴力修改，暴力复合，这样的话复杂度是\(O(n\log^3n)\)的。也许能过。

但是你会发现这个函数具有特殊性质，具体的，除了一个点取到特殊值以外，其它都是常值函数，也就是说可以\(O(1)\)复合，实现一个struct即可做到\(O(n\log ^2n)\)

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=3e5+5,M=N*4+5,K=(1<<10)+5,mod=998244353,Mod=mod-1;ll INF=1e18+7;const db eps=1e-5;mt19937 rnd(time(0));
int n,m,k,x,y,z,fa[N],Ans[N],d[N],Si[N],Sn[N],Id[N],Tp[N],Ih,Fl[N][20],En[N];vector<int> S[N];
struct Node{int p1,p,p2,w1,w2;Node operator +(const Node &B)const{Node C;C.w1=w1;C.w2=w2;C.p=p;p1^B.p?(C.p1=B.p1,C.w1+=B.w1):(C.p1=B.p2,C.w1+=B.w2);p2^B.p?(C.p2=B.p1,C.w2+=B.w1):(C.p2=B.p2,C.w2+=B.w2);return C;}};
namespace Tree{
	#define ls v<<1
	#define rs v<<1|1
	Node f[M];void Up(int v){f[v]=f[rs]+f[ls];}void Ins(int x,Node y,int l=1,int r=n,int v=1){if(l==r) {f[v]=y;return;}int m=l+r>>1;x<=m?Ins(x,y,l,m,ls):Ins(x,y,m+1,r,rs);Up(v);}
	Node Qry(int x,int y,int l=1,int r=n,int v=1){if(x<=l&&r<=y) return f[v];int m=l+r>>1;if(y<=m) return Qry(x,y,l,m,ls);if(x>m)return Qry(x,y,m+1,r,rs);return Qry(x,y,m+1,r,rs)+Qry(x,y,l,m,ls);}
	#undef ls
	#undef rs
}
void dfs1(int x,int La){d[x]=d[La]+1;Si[x]=1;for(int i:S[x]) i^La&&(dfs1(i,x),Si[x]+=Si[i],Si[i]>Si[Sn[x]]&&(Sn[x]=i));}
void dfs2(int x,int La){Tp[x]=La;Id[x]=++Ih;if(!Sn[x]) return;dfs2(Sn[x],La);for(int i:S[x]) i^fa[x]&&i^Sn[x]&&(dfs2(i,i),0);}
Node Find(int x){Node C;C.p1=0;while(Fl[x][C.p1]) C.p1++;C.p=C.p1;C.p2=C.p1+1;while(Fl[x][C.p2]) C.p2++;C.w1=C.p1;C.w2=C.p2;return C;}
int main(){
	freopen("1.in","r",stdin);
	int i,j;scanf("%d",&n);n++;for(i=2;i<=n;i++) scanf("%d",&fa[i]),S[fa[i]].PB(i);dfs1(1,0);dfs2(1,1);Tree::Ins(Id[1],Find(1));En[1]=1;
	for(i=2;i<=n;i++){Ans[i]=Ans[i-1];
		x=fa[i];while(x){Node p=Tree::Qry(Id[Tp[x]],En[Tp[x]]);Ans[i]-=p.w1;(x=fa[Tp[x]])&&(Fl[x][p.p1]--);}En[Tp[i]]=Id[i];Tree::Ins(Id[i],Find(i));
		x=i;while(x){Node p=Tree::Qry(Id[Tp[x]],En[Tp[x]]);Ans[i]+=p.w1;(x=fa[Tp[x]])&&(Fl[x][p.p1]++,Tree::Ins(Id[x],Find(x)),0);}printf("%d\n",Ans[i]); 
	}
}

原文地址：http://www.cnblogs.com/275307894a/p/16894826.html