BZOJ 1036 ZJOI2008 树的统计Count 【LCT模板】

tonyfang posted @ 2016年2月15日 15:51 in BZOJ with tags c++ OI , 488 阅读

学了一发LCT,感觉自己萌萌哒~

 

 

# include <stdio.h>
# include <algorithm>
 
using namespace std;

const int M=203000;
int fa[M],ch[M][2],sz[M];
long long val[M],sum[M],maxx[M];
bool rev[M];

inline bool isroot(int x) {
	return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
inline long long max(long long a,long long b) {
	return a>b?a:b;
}
inline void pushup(int x) {
	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
	maxx[x]=max(val[x],max(maxx[ch[x][0]],maxx[ch[x][1]]));	
}
inline void pushdown(int x) {
	if(rev[x]) {
		rev[x]^=1;
		rev[ch[x][0]]^=1;
		rev[ch[x][1]]^=1;
		swap(ch[x][0],ch[x][1]);
	}
}
inline void rotate(int x) {
	int y=fa[x],z=fa[y],p=ch[y][1]==x;
	if(!isroot(y)) ch[z][ch[z][1]==y]=x;
	fa[ch[x][p^1]]=y;ch[y][p]=ch[x][p^1];
	fa[y]=x,fa[x]=z;ch[x][p^1]=y;
	pushup(y);
	pushup(x);
}
int q[M*2],qn=0;
inline void splay(int x) {
	q[++qn]=x;
	for (int i=x;!isroot(i);i=fa[i]) q[++qn]=fa[i];
	while(qn) pushdown(q[qn--]);
	while(!isroot(x)) {
		int y=fa[x],z=fa[y];
		if(!isroot(y)) {
			if((ch[y][0]==x)^(ch[z][0]==y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
inline void access(int x) {
	for (int t=0;x;t=x,x=fa[x]) splay(x),ch[x][1]=t,pushup(x);
}
inline void makeroot(int x) {
	access(x);splay(x);rev[x]^=1;
}
inline void link(int x,int y) {
	makeroot(x);fa[x]=y;
}
inline void getdata(int x,int y) {
	makeroot(x);access(y);splay(y);
}
inline void cut(int x,int y) {
	getdata(x,y);ch[y][0]=fa[x]=0;
}
int n,u[M],v[M],Q;char opt[9];
int main() {
	scanf("%d",&n);maxx[0]=-200011300;
	for (int i=1;i<n;++i) scanf("%d%d",&u[i],&v[i]);
	for (int i=1;i<=n;++i) scanf("%lld",&val[i]),maxx[i]=sum[i]=val[i];
	for (int i=1;i<n;++i) link(u[i],v[i]);
	scanf("%d",&Q);
	while(Q--) {
		scanf("%s",opt);
		int ly,cdl;
		scanf("%d%d",&ly,&cdl);
		if(opt[1]=='H') splay(ly),val[ly]=cdl,pushup(ly);
		if(opt[1]=='S') getdata(ly,cdl),printf("%lld\n",sum[cdl]);
		if(opt[1]=='M') getdata(ly,cdl),printf("%lld\n",maxx[cdl]);
	}
	return 0;
}
refrigerationpedia.c 说:
2023年4月24日 18:48

Learn why your refrigerator or air conditioner isn’t cooling properly and how to properly fill your refrigerator or air conditioner’s gas tank. Reasons behind a noisy air conditioner or refrigerator Reasons behind the refrigerationpedia.com refrigerator not freezing ice properly, Reasons for water leakage from the refrigerator and AC. Reasons behind the refrigerator not freezing ice properly.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter