记录编号	269642	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.152 s
提交时间	2016-06-13 20:11:50	内存使用	1.12 MiB

#include<cstdio>
#include<cstring>
#include<cctype>
#define lch(rt) rt<<1
#define rch(rt) rt<<1|1
const int maxn=10005;
struct edge{
	int to,next,dis,num;
}lst[maxn<<1];int len=1;
int first[maxn];
void addedge(int a,int b,int w,int i){
	lst[len].num=i;
	lst[len].dis=w;
	lst[len].to=b;
	lst[len].next=first[a];
	first[a]=len++;
}
bool neg[maxn<<2];
int Max[maxn<<2];
int Min[maxn<<2];
void swap(int &a,int &b){
	int tmp=a;
	a=-b;
	b=-tmp;
}
void pushdown(int rt){
	if(neg[rt]){
		swap(Max[lch(rt)],Min[lch(rt)]);
		swap(Max[rch(rt)],Min[rch(rt)]);
		neg[lch(rt)]^=1;neg[rch(rt)]^=1;
		neg[rt]=0;
	}
}
int max(int a,int b){
	return a>b?a:b;
}
int min(int a,int b){
	return a<b?a:b;
}
void insert(int rt,int l,int r,int k,int w){
	if(l==r){
		Min[rt]=Max[rt]=w;
		return;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(k<=mid)insert(lch(rt),l,mid,k,w);
	else insert(rch(rt),mid+1,r,k,w);
	Max[rt]=max(Max[lch(rt)],Max[rch(rt)]);
	Min[rt]=min(Min[lch(rt)],Min[rch(rt)]);
}
void negate(int rt,int l,int r,int a,int b){
	if(a<=l&&r<=b){
		neg[rt]^=1;
		swap(Max[rt],Min[rt]);
		return;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(a<=mid)negate(lch(rt),l,mid,a,b);
	if(b>mid)negate(rch(rt),mid+1,r,a,b);
	Max[rt]=max(Max[lch(rt)],Max[rch(rt)]);
	Min[rt]=min(Min[lch(rt)],Min[rch(rt)]);
}
int query(int rt,int l,int r,int a,int b){
	if(a<=l&&r<=b)return Max[rt];
	pushdown(rt);
	int mid=(l+r)>>1;
	if(b<=mid)return query(lch(rt),l,mid,a,b);
	if(a>mid)return query(rch(rt),mid+1,r,a,b);
	return max(query(lch(rt),l,mid,a,b),query(rch(rt),mid+1,r,a,b));
}
int top[maxn],depth[maxn],edgew[maxn],_s[maxn],prt[maxn],point[maxn],pos[maxn];
void dfs1(int x){
	_s[x]=1;
	for(int pt=first[x];pt;pt=lst[pt].next){
		if(lst[pt].to==prt[x])continue;
		depth[lst[pt].to]=depth[x]+1;
		prt[lst[pt].to]=x;
		point[lst[pt].num]=lst[pt].to;
		edgew[lst[pt].to]=lst[pt].dis;
		dfs1(lst[pt].to);
		_s[x]+=_s[lst[pt].to];
	}
}
int T=0;int n;
void dfs2(int x){
	pos[x]=++T;
	insert(1,1,n,pos[x],edgew[x]);
	int hvy=0;
	for(int pt=first[x];pt;pt=lst[pt].next){
		if(lst[pt].to==prt[x])continue;
		if(_s[lst[pt].to]>_s[hvy])hvy=lst[pt].to;
	}
	if(hvy){
		top[hvy]=top[x];
		dfs2(hvy);
		for(int pt=first[x];pt;pt=lst[pt].next){
			if(lst[pt].to==prt[x]||lst[pt].to==hvy)continue;
			top[lst[pt].to]=lst[pt].to;
			dfs2(lst[pt].to);
		}
	}
}
void negate(int u,int v){
	int t1=top[u],t2=top[v];
	while(t1!=t2){
		if(depth[t1]>depth[t2]){
			negate(1,1,n,pos[t1],pos[u]);
			u=prt[t1];
			t1=top[u];
		}else{
			negate(1,1,n,pos[t2],pos[v]);
			v=prt[t2];
			t2=top[v];
		}
	}
	if(u==v)return;
	if(depth[u]>depth[v])negate(1,1,n,pos[v]+1,pos[u]);
	else negate(1,1,n,pos[u]+1,pos[v]);
}
int getmax(int u,int v){
	int ans=0xefffffff;
	int t1=top[u],t2=top[v];
	while(t1!=t2){
		if(depth[t1]>depth[t2]){
			ans=max(ans,query(1,1,n,pos[t1],pos[u]));
			u=prt[t1];
			t1=top[u];
		}else{
			ans=max(ans,query(1,1,n,pos[t2],pos[v]));
			v=prt[t2];
			t2=top[v];
		}
	}
	if(u==v)return ans;
	if(depth[u]>depth[v])ans=max(ans,query(1,1,n,pos[v]+1,pos[u]));
	else ans=max(ans,query(1,1,n,pos[u]+1,pos[v]));
	return ans;
}
void read(int &x){
	char ch;bool minus=false;
	while(ch=getchar(),!isdigit(ch)&&ch!='-');
	if(ch=='-'){
		minus=true;
		ch=getchar();
	}
	x=ch-'0';
	while(ch=getchar(),isdigit(ch))x=x*10+ch-'0';
	if(minus)x=-x;
}
int main(){
	freopen("maintaintree.in","r",stdin);
	freopen("maintaintree.out","w",stdout);
	read(n);
	int u,v,w;
	for(int i=1;i<n;++i){
		read(u);read(v);read(w);
		addedge(u,v,w,i);
		addedge(v,u,w,i);
	}
	depth[1]=1;
	dfs1(1);
	top[1]=1;
	dfs2(1);
	char buf[10];
	while(scanf("%s",buf),buf[0]!='D'){
		read(u);read(v);
		if(buf[0]=='C'){
			insert(1,1,n,pos[point[u]],v);
		}else if(buf[0]=='N'){
			negate(u,v);
		}else{
			printf("%d\n",getmax(u,v));
		}
	}
	fclose(stdin);fclose(stdout);
	return 0;
}