记录编号	481401	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	1.621 s
提交时间	2018-01-02 18:51:29	内存使用	7.98 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 201000
#define lc(x) (ch[x][0])
#define rc(x) (ch[x][1])
int ch[N][2],fa[N];
int ma[N],mi[N],reverse[N],fan[N],v[N];
int n,sz;
int get(int x){return rc(fa[x])==x;}
void update(int x){
	if(x){
		ma[x]=max(ma[lc(x)],ma[rc(x)]);
		mi[x]=min(mi[lc(x)],mi[rc(x)]);
		if(x>n) ma[x]=max(ma[x],v[x]),mi[x]=min(mi[x],v[x]);
	}
}
void my_swap(int x){
	int temp=mi[x];mi[x]=-ma[x];ma[x]=-temp;
}
void pushdown(int x){
	if(x){
		if(reverse[x]){
			swap(lc(x),rc(x));
			if(lc(x)) reverse[lc(x)]^=1;
			if(rc(x)) reverse[rc(x)]^=1;
			reverse[x]=0;
		}
		if(fan[x]){
			if(lc(x)) fan[lc(x)]^=1,v[lc(x)]=-v[lc(x)];
			if(rc(x)) fan[rc(x)]^=1,v[rc(x)]=-v[rc(x)];
			my_swap(lc(x));my_swap(rc(x));
			fan[x]=0;
		}
	}
}
int isroot(int x){return lc(fa[x])!=x&&rc(fa[x])!=x;}
void rotate(int x){
	int old=fa[x],oldf=fa[old];int d=get(x);
	if(!isroot(old)) ch[oldf][rc(oldf)==old]=x;
	fa[x]=oldf;
	ch[old][d]=ch[x][d^1];fa[ch[old][d]]=old;
	ch[x][d^1]=old;fa[old]=x;
	update(old);update(x);
}
int stack[N],hea;
void splay(int x){
	hea=0;stack[++hea]=x;
	for(int i=x;!isroot(i);i=fa[i])	stack[++hea]=fa[i];
	pos2(i,hea,1) pushdown(stack[i]);
	for(int f;!isroot(x);rotate(x)){
		if(!isroot(f=fa[x])) rotate((get(f)==get(x))?f:x);
	}	
}
void access(int x){
	for(int t=0;x;t=x,x=fa[x]){
		splay(x);rc(x)=t;update(x);
	}
}
void makeroot(int x){
	access(x);splay(x);reverse[x]^=1;
}
void link(int x,int y){
	makeroot(x);fa[x]=y;
}
int query(int x,int y){
	makeroot(x);access(y);splay(y);return ma[y];
}
void Negate(int x,int y){
	makeroot(x);access(y);splay(y);fan[y]^=1;my_swap(y);v[y]=-v[y];
}
void change(int x,int y){
	makeroot(x);v[x]=y;update(x);
}
int cun[N];
int main(){
	freopen("maintaintree.in","r",stdin);
	freopen("maintaintree.out","w",stdout);
	scanf("%d",&n);
	memset(mi,0x3f,sizeof(mi));
	memset(ma,-0x3f,sizeof(ma));
	pos(i,1,n-1){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);++sz;
		int id=sz+n;
		ma[id]=mi[id]=v[id]=z;link(x,id);link(id,y);
		cun[i]=id;
	}
	while(1){
		char s[10];scanf("%s",s);
		if(s[0]=='D') break;
		int x,y;scanf("%d%d",&x,&y);
		if(s[0]=='Q') printf("%d\n",query(x,y));
		if(s[0]=='N') Negate(x,y);
		if(s[0]=='C') change(cun[x],y);
	}
	return 0;
}