记录编号	144353	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.846 s
提交时间	2014-12-22 19:09:56	内存使用	1.01 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define Maxn 10010
#define l(x) ch[x][0]
#define r(x) ch[x][1]
#define isroot(x) (!fa[x]||(l(fa[x])!=x&&r(fa[x])!=x))
using namespace std;
struct node{
	int y,to,v;
}E[Maxn<<1]={0};
int n,m,g[Maxn]={0},map[Maxn]={0},tot=1;
int ch[Maxn][2]={0},fa[Maxn]={0};
int maxt[Maxn<<1]={0},mint[Maxn<<1]={0};
int a[Maxn]={0},negt[Maxn<<1]={0};
char str[21];
void update(int x){
	mint[x]=maxt[x]=a[x];
	if(l(x)){
		mint[x]=min(mint[x],mint[l(x)]);
		maxt[x]=max(maxt[x],maxt[l(x)]);
	}
	if(r(x)){
		mint[x]=min(mint[x],mint[r(x)]);
		maxt[x]=max(maxt[x],maxt[r(x)]);
	}
}
void addnode(int x,int y,int v){
	E[++tot].y=y; E[tot].v=v; E[tot].to=g[x]; g[x]=tot;
	E[++tot].y=x; E[tot].v=v; E[tot].to=g[y]; g[y]=tot;
}
void chan(int x){
	if(x){
		negt[x]^=1; a[x]=-a[x];
		maxt[x]=-maxt[x];
		mint[x]=-mint[x];
		swap(maxt[x],mint[x]);
	}
}
void clean(int x){
	if(x&&negt[x]){
		chan(l(x)); chan(r(x));
		negt[x]=0;
	}
}
void zig(int x){
	int f1,f2;
	f1=fa[x]; f2=fa[f1];
	if(l(f2)==f1) l(f2)=x;
	else if(r(f2)==f1) r(f2)=x; fa[x]=f2;
	fa[r(x)]=f1; l(f1)=r(x); fa[f1]=x; r(x)=f1;
	update(f1);
}
void zag(int x){
	int f1,f2;
	f1=fa[x]; f2=fa[f1];
	if(l(f2)==f1) l(f2)=x;
	else if(r(f2)==f1) r(f2)=x; fa[x]=f2;
	fa[l(x)]=f1; r(f1)=l(x); fa[f1]=x; l(x)=f1;
	update(f1);
}
void splay(int x){
	int f1,f2;
	clean(x);
	while(!isroot(x)){
		f1=fa[x];
		f2=fa[f1];
		if(isroot(f1)){
			clean(f1); clean(x);
			if(l(f1)==x) zig(x);
			else zag(x);
		}
		else{
			clean(f2); clean(f1); clean(x);
			if(l(f2)==f1){
				if(l(f1)==x) zig(x),zig(x);
				else zag(x),zig(x);
			}
			else if(r(f2)==f1){
				if(l(f1)==x) zig(x),zag(x);
				else zag(x),zag(x);
			}
		}
	}
	update(x);
}
bool vis[Maxn]={0};
void dfs(int x){
	vis[x]=true;
	for(int i=g[x];i;i=E[i].to){
		int p=E[i].y;
		if(vis[p]) fa[x]=p;
		else{
			a[p]=E[i].v;
			map[i>>1]=p;
			dfs(p);
		}
	}
}

void access(int x){
	int y=0;
	while(x){
		splay(x); clean(x);
		r(x)=y; y=x; update(x); x=fa[x];
	}
}
void work(int u,int v){
	access(v);
	for(v=0;u;u=fa[u]){
		splay(u);
		if(!fa[u]){
			chan(v);
			chan(r(u));
			return;
		}
		clean(u);
		r(u)=v;v=u;update(u);
	}
}
void qmax(int u,int v){
	access(v);
	for(v=0;u;u=fa[u]){
		splay(u);
		if(!fa[u]){
			printf("%d\n",max(maxt[v],maxt[r(u)]));
			return;
		}
		clean(u);
		r(u)=v; v=u; update(u);
	}
}
void change(int x,int y){
	splay(x); a[x]=y;
}
void init(){
	int x,y,z;
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		addnode(x,y,z);
	}
	maxt[0]=-0x7f7f7f7fLL;
	mint[0]=0x7f7f7f7fLL;
	dfs(1);
	while(1){
		scanf("%s%d%d",str,&x,&y);
		if(str[0]=='C') change(map[x],y);
		else if(str[0]=='N') work(x,y);
		else if(str[0]=='Q') qmax(x,y);
		else break;
	}
}
int main(){
	freopen("maintaintree.in","r",stdin);
	freopen("maintaintree.out","w",stdout);
	init();
	return 0;
}
/*
5
2 1 8
1 3 4
4 1 3
5 3 7
NEGATE 1 4
CHANGE 1 9
CHANGE 1 9
QUERY 5 1
QUERY 3 1
CHANGE 3 6
DONE
*/
/*
5
2 1 8
1 3 4
4 1 3
5 3 7
NEGATE 1 4
CHANGE 1 9
NEGATE 2 1
CHANGE 1 9
NEGATE 5 1
NEGATE 2 1
QUERY 5 1
QUERY 3 1
CHANGE 3 6
NEGATE 3 1
DONE
*/