记录编号	334937	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.199 s
提交时间	2016-11-01 19:30:26	内存使用	5.63 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
struct edge{int f,t,l,p;}w[N];
int n,head[N],tail[N],next[N];
void add(int f,int num){
	if (!head[f]) head[f]=tail[f]=num;
		else tail[f]=next[tail[f]]=num;
}
int fa[N],son[N][2],v[N],ma[N],mi[N];
bool root[N],rev[N],neg[N],E[N];//是否是边
#define lc son[x][0]
#define rc son[x][1]
void Neg(int x){
	neg[x]^=1;
	v[x]=-v[x];ma[x]=-ma[x];mi[x]=-mi[x];
	swap(mi[x],ma[x]);
}
void update(int x){
	if (E[x]) ma[x]=mi[x]=v[x];
		else ma[x]=-1e9,mi[x]=1e9;
	if (lc) ma[x]=max(ma[x],ma[lc]),mi[x]=min(mi[x],mi[lc]);
	if (rc) ma[x]=max(ma[x],ma[rc]),mi[x]=min(mi[x],mi[rc]);
}
void pushdown(int x){
	if (rev[x]){
		swap(son[lc][0],son[lc][1]);
		swap(son[rc][0],son[rc][1]);
		rev[lc]^=1;rev[rc]^=1;
		rev[x]=rev[0]=0;
	}
	if (neg[x]){
		Neg(lc);Neg(rc);
		neg[x]=neg[0]=0;
	}
}
void rotate(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (y==son[z][0]) son[z][0]=x;else
	if (y==son[z][1]) son[z][1]=x;
	root[x]=root[y];root[y]=0;
	update(y);update(x);
}
void splay(int x){
	pushdown(x);
	while (!root[x]){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (root[y]){rotate(x);return;}
		if (x==son[y][0]) rotate(y==son[z][0]?y:x);
			else rotate(y==son[z][1]?y:x);
		rotate(x);
	}
}
void access(int x){
	splay(x);
	root[rc]=1;rc=0;
	update(x);
	while (fa[x]){
		int y=fa[x];
		splay(y);
		root[son[y][1]]=1;
		root[son[y][1]=x]=0;
		update(y);
		splay(x);
	}
}
void make_root(int x){
	access(x);
	rev[x]^=1;
	swap(lc,rc);
}
int cnt;
void dfs(int x){
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i].t]){
		fa[fa[w[i].t]=++cnt]=x;
		root[cnt]=E[cnt]=1;
		ma[cnt]=mi[cnt]=v[cnt]=w[i].l;
		w[i].p=w[i<n?i+n:i-n].p=cnt;
		dfs(w[i].t);
	}
}
int main()
{
	freopen("maintaintree.in","r",stdin);
	freopen("maintaintree.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<n;i++){
		scanf("%d%d%d",&w[i].f,&w[i].t,&w[i].l);
		w[i+n]=w[i];swap(w[i].f,w[i].t);
		add(w[i].f,i);add(w[i].t,i+n);
	}
	for (int i=1;i<=n;i++)
		root[i]=1,ma[i]=-1e9,mi[i]=1e9;
	cnt=n;fa[1]=1;dfs(1);fa[1]=0;
	while (1){
		char s[20];int a,b;
		scanf("%s%d%d",s,&a,&b);
		if (s[0]=='D') break;
		if (s[0]=='C'){
			access(w[a].p);
			v[w[a].p]=b;
			update(w[a].p);
		}
		else make_root(a),access(b);
		if (s[0]=='N') Neg(b);
		if (s[0]=='Q') printf("%d\n",ma[b]);
	}
	return 0;
}