c/c++语言开发共享20200726模拟赛 C.树高

待填。

人生第一次在$AC$AC前有90次提交记录的题。
人生第一次写了$10K$10K代码的题（写完$6KTreap$6KTreap发现$TLE$TLE的死死的然后开始写$7KSplay$7KSplay然后卡了一个世纪。）

$mathcal AC Code$AC Code

#include<bits/stdc++.h> #define maxn 200005 #define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++) #define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--) #define C 31 #define lim 17 #define il inline using namespace std;  char Start; namespace IO{ 	char cb[1<<16] ,*cs=cb,*ct=cb; 	#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<16,stdin),cs==ct)?0:*cs++) 	inline void read(int &res){ 		char ch;bool f = 0; 		for(;!isdigit(ch=getc());) if(ch == '-') f = 1; 		for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); 		(f) && (res = -res); 	} 	char wb[1 << 23] , *ws = wb; 	inline void print(int a,char c){ 		static int q[20]={}; 		if(a < 0) *ws ++ = '-' , a = -a; 		for(;a; a/= 10) q[++q[0]] = a % 10; 		if(!q[0]) *ws++ = '0'; 		for(;q[0];) *ws++ = '0' + q[q[0] --]; 		*ws ++ = c; 	} 	void flush(){ 		fwrite(wb,1,ws-wb,stdout); 		ws = wb; 	} }  using IO :: print; using IO :: flush; using IO :: read;  int n,f[lim][maxn]; int rt[maxn][C+1] , dep[maxn] , st[maxn] , ed[maxn]; int fa[maxn] , ch[maxn][2] , sz[maxn][C+1] , xsz[maxn][C+1] , col[maxn] , rot[maxn] , tgrt[maxn] , tgcl[maxn] , mx[maxn] , mn[maxn] , key[maxn];  int Gets(int u,int v){ 	per(i,lim-1,0) if(dep[f[i][u]] > dep[v]) 		u = f[i][u]; 	return u; }  il void dtrt(int u,int x){ 	if(!u) return ; 	tgrt[u] = x , rot[u] = x; }  il void dtcl(int u,int x){ 	if(!u) return ; 	tgcl[u] = x , col[u] = x; }  il void dt(int u){ 	if(!u) return ; 	if(tgrt[u] != -1) dtrt(ch[u][0] , tgrt[u]) , dtrt(ch[u][1] , tgrt[u]) , tgrt[u] = -1; 	if(tgcl[u] != 0) dtcl(ch[u][0] , tgcl[u]) , dtcl(ch[u][1] , tgcl[u]) , tgcl[u] = 0; }  il void upd(int u){ 	if(!u) return ; 	int i=0 , l = ch[u][0] , r = ch[u][1] , *su = sz[u] , *sl = sz[l] , *sr = sz[r] , *xsu = xsz[u]; 	for(;i+7<=C;i+=8)  		su[i] = sl[i] + sr[i] + xsu[i], 		su[i+1] = sl[i+1] + sr[i+1] + xsu[i+1], 		su[i+2] = sl[i+2] + sr[i+2] + xsu[i+2], 		su[i+3] = sl[i+3] + sr[i+3] + xsu[i+3], 		su[i+4] = sl[i+4] + sr[i+4] + xsu[i+4], 		su[i+5] = sl[i+5] + sr[i+5] + xsu[i+5], 		su[i+6] = sl[i+6] + sr[i+6] + xsu[i+6], 		su[i+7] = sl[i+7] + sr[i+7] + xsu[i+7]; /*	su[i] = sl[i] + sr[i] + xsu[i], 	su[i+1] = sl[i+1] + sr[i+1] + xsu[i+1], 	su[i+2] = sl[i+2] + sr[i+2] + xsu[i+2], 	su[i+3] = sl[i+3] + sr[i+3] + xsu[i+3], 	su[i+4] = sl[i+4] + sr[i+4] + xsu[i+4], 	su[i+5] = sl[i+5] + sr[i+5] + xsu[i+5], 	su[i+6] = sl[i+6] + sr[i+6] + xsu[i+6];*/  	mx[u] = mn[u] = dep[(u+1) / 2] ,  	mx[u] = max(mx[u] , max(mx[l] , mx[r])); 	mn[u] = min(mn[u] , min(mn[l] , mn[r])); }  il int inr(int u){ return ch[fa[u]][1] == u; } il int isr(int u){ return fa[u] == 0; }  void rotate(int x){ 	int y = fa[x] , z = fa[y] , c = inr(x); 	if(!isr(y)) ch[z][inr(y)] = x; 	(ch[y][c] = ch[x][!c]) && (fa[ch[y][c]] = y); 	fa[fa[ch[x][!c]=y]=x]=z; 	upd(y); }  void dtpath(int u){ 	if(fa[u]) dtpath(fa[u]); 	dt(u); }  void splay(int u,int goal){ 	if(!u) return; 	for(dtpath(u);fa[u] != goal;rotate(u)) 		if(fa[fa[u]] != goal) 			rotate(inr(fa[u]) ^ inr(u) ? u : fa[u]); 	upd(u); }  void merge(int &u,int l,int r){ 	if(!l || !r) return (void)(u = l + r); 	splay(r,0); 	for(;ch[r][0];r = ch[r][0]); 	splay(r,0); 	splay(l,0); 	ch[r][0] = l , fa[l] = r; 	upd(r); 	u = r; }  void split(int &u,int &l,int &r,int v){ 	splay(v,0); 	r = ch[v][1]; 	ch[v][1] = fa[ch[v][1]] = 0; 	l = v; 	upd(v); }  void split(int &u,int &a,int &b,int &c,int A,int B){ 	splay(A,0); 	a = ch[A][0]; 	fa[a] = ch[A][0] = 0; 	upd(A); 	 	splay(B,0); 	c = ch[B][1]; 	fa[c] = ch[B][1] = 0; 	upd(B); 	 	b = B; }  int serk(int u,int pr = 0){ 	int r = pr ? (ch[u][1] == pr) * (sz[ch[u][0]][0] + 1) : (sz[ch[u][0]][0] + 1); 	if(fa[u]) r += serk(fa[u],u); 	dt(u); 	return r; } il int sert(int u){ 	for(;fa[u]; u = fa[u]); 	return u; }  void ins(int u,int x){  	int v = f[0][u];  	merge(rt[u][x],rt[u][x],ed[u]); 	merge(rt[u][x],st[u],rt[u][x]); 	dtcl(rt[u][x] = sert(rt[u][x]) , x);  	dtpath(st[v]); 	if(col[st[v]] != x){ 		dtrt(rt[u][x] , v); 		merge(rt[v][x],rt[v][x],rt[u][x]); 		xsz[st[v]][x] ++; 	} 	else{ 		int p = rot[st[v]] , a , b; 		dtrt(rt[u][x] , p); 		split(rt[p][x] , a , b , st[v]); 		merge(rt[p][x] , a , rt[u][x]); 		merge(rt[p][x] , rt[p][x] , b); 	} 	splay(st[v],0); 	rt[u][x] = 0; }  void del(int u,bool flg = 1){ 	dtpath(st[u]); 	int x = col[st[u]]; 	int p = rot[st[u]] , a , b , c; 	 	split(rt[p][x],a,rt[u][x],c,st[u],ed[u]); 	merge(rt[p][x] , a , c); 	serk(st[f[0][u]]); 	if(col[st[f[0][u]]] != x){ 		xsz[st[f[0][u]]][x] --; 	} 	xsz[st[u]][x] += sz[rt[u][x]][0] - 2; 	 	a = rt[u][x]; 	splay(a,0); 	dtrt(rt[u][x],u); 	for(;ch[a][0];a = ch[a][0]); 	splay(a,0); 	b = ch[a][1]; 	ch[a][1] = fa[b] = 0; 	upd(a); 	splay(b,0); 	for(;ch[b][1];b = ch[b][1]); 	splay(b,0); 	rt[u][x] = ch[b][0]; 	fa[rt[u][x]] = ch[b][0] = 0; 	upd(b); 	 	splay(st[f[0][u]],0); }  int ar[maxn];  void ser(int u,int x){ 	if(rt[(u+1)/2][x]) 		ar[++ar[0]] = (u+1)/2; 	if(sz[ch[u][0]][x]) 		ser(ch[u][0] , x); 	if(sz[ch[u][1]][x]) 		ser(ch[u][1] , x); }  char End;  int main(){ 	 //	cerr << (&End - &Start) / 1024 / 1024  << endl; 	 	freopen("shu.in","r",stdin); 	freopen("shu.out","w",stdout);  	int ts = 0; 	 	read(n);dep[0] = -1; 	memset(tgrt,-1,sizeof tgrt);mn[0] = 0x3f3f3f3f; 	rep(i,1,n) st[i] = i * 2 - 1 , ed[i] = st[i] + 1; 	rep(i,2,n) read(f[0][i]) , dep[i] = dep[f[0][i]] + 1; 	rep(i,1,n) mx[st[i]] = mn[st[i]] = mx[ed[i]] = mn[ed[i]] = dep[i]; 	rep(i,1,2*n)  xsz[i][0] = 1 , sz[i][0] = 1; 	rep(j,1,lim-1) rep(i,1,n) f[j][i] = f[j-1][f[j-1][i]]; 	rep(i,1,n){ 		int x; 		read(x); 		ins(i,x); 	//	rep(i,1,10) printf("@%d %d %d %dn",i,fa[i],ch[i][0],ch[i][1]); 	} 	int m;read(m); 	for(int op,x,y;m--;){ 		read(op),read(x); 		if(op == 1){ 			read(y);serk(st[x]); 			if(y != col[st[x]]) 				del(x), 				ins(x,y); 		} 		if(op == 2){ 			read(y);splay(st[x],0); 			if(y != col[st[x]]){ 				 				int u = st[x] , p = Gets(x , rot[u]) , R = rot[u] , cl = col[u]; 				int a , b , c; 				split(rt[R][cl],a,b,c,st[p],ed[p]); 				merge(rt[R][cl],a,c);	 				xsz[st[R]][cl] --; 				 				ar[0] = 0;b = sert(b); 				ser(b , y); 				 				rep(i,1,ar[0]){ 					int e = ar[i]; 					xsz[st[e]][y] = 0; 					swap(rt[e][y] , rt[e][cl]); 					rt[e][cl] = sert(rt[e][cl]); 					dtcl(rt[e][cl] , cl); 					 					int rse = serk(st[e]) , c , d , f; 					split(b,c,d,st[e]); 					merge(b,c,rt[e][cl]), 					merge(b,b,d); 					rt[e][cl] = 0; 					splay(st[e],0); 				} 				 				splay(b,0); 				dtcl(b , y);dtpath(st[R]); 				if(col[st[R]] != y){ 					dtrt(b,R); 					merge(rt[R][y],rt[R][y],b); 					xsz[st[R]][y] ++; 				} 				else{ 					int p = rot[st[R]] , a , c; 					dtrt(b, p);	 					split(rt[p][y] , a , c , st[R]); 					merge(rt[p][y] , b , c); 					merge(rt[p][y] , a , rt[p][y]); 				} 				splay(st[R],0); 			} 		} 		if(op == 3){ 			dtpath(st[x]); 			int u = st[x] , p = Gets(x , rot[u]) , R = rot[u] , cl = col[u]; 			int a , b , c; 			split(rt[R][cl],a,b,c,st[p],ed[p]); 			 			b = sert(b); 			print(col[u],' '); 			print(sz[b][0]/2,' '); 			print(mx[b]-mn[b]+1,'n'); 			 			merge(rt[R][cl] , a , b); 			merge(rt[R][cl] , rt[R][cl] , c) ;  		} 		if(m % 1000 == 0)		 			flush(); 	} } 

c/c++开发分享20200726模拟赛 C.树高地址：https://blog.csdn.net/qq_35950004/article/details/107604752