记录编号	324255	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	森林	是否通过	通过
代码语言	C++	运行时间	1.121 s
提交时间	2016-10-17 21:22:28	内存使用	1.47 MiB

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=10100;
struct E{
	int to,next,w,num;
};E e[maxn<<1];  //dfs序中下标为i的点    点在dfs序中的下标
int head[maxn],len=0,dfn_t=0,dfn[maxn],id[maxn],deep[maxn],fa[maxn],top[maxn],size[maxn],son[maxn];
int val[maxn],change[maxn],t_max[maxn<<2],t_min[maxn<<2],n,lazy[maxn<<2];
inline void add(const int& from,const int& to,const int& w,const int&id){
	e[++len].to=to;
	e[len].w=w;
	e[len].num=id;
	e[len].next=head[from];
	head[from]=len;
}
inline void dfs(const int& x){
	size[x]=1;son[x]=0;
	for(int i=head[x];i!=-1;i=e[i].next){
		if(deep[e[i].to])continue;
		deep[e[i].to]=deep[x]+1;
		fa[e[i].to]=x;
		val[e[i].to]=e[i].w;
		change[e[i].num]=e[i].to;
		dfs(e[i].to);
		size[x]+=size[e[i].to];
		if(size[e[i].to]>size[son[x]])son[x]=e[i].to;
	}
}
inline void dfs(const int& x,const int& tp){
	top[x]=tp;dfn[++dfn_t]=x;id[x]=dfn_t;
	if(son[x])dfs(son[x],tp);
	for(int i=head[x];i!=-1;i=e[i].next){
		if(id[e[i].to])continue;
		dfs(e[i].to,e[i].to);
	}
}
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define mid ((l+r)>>1)
inline void update(const int& rt){
	t_max[rt]=max(t_max[rt<<1],t_max[rt<<1|1]);
	t_min[rt]=min(t_min[rt<<1],t_min[rt<<1|1]);
}
inline void build(const int& rt,const int& l,const int& r){
	if(l==r){
		t_max[rt]=t_min[rt]=val[dfn[l]];
		return;
	}
	build(lson);
	build(rson);
	update(rt);
}
int ql,qr,res;
inline void ch(const int & rt){
	t_min[rt]=-t_min[rt];
	t_max[rt]=-t_max[rt];
	swap(t_min[rt],t_max[rt]);
	lazy[rt]^=1;
}
inline void pushdown(const int&rt){
	ch(rt<<1);
	ch(rt<<1|1);
	lazy[rt]=0;
}
inline void query(const int & rt,const int& l,const int& r){
	if(ql<=l&&qr>=r){
		res=max(res,t_max[rt]);
		return;
	}
	if(lazy[rt])pushdown(rt);
	if(ql<=mid)query(lson);
	if(qr>mid)query(rson);
	update(rt);
}
inline int query(int l,int r){
	ql=l;qr=r;
	res=-0x7fffffff;
	query(1,1,n);
	return res;
}
inline int tree_query(int x,int y){
	int ans=-0x7fffffff;
	while(top[x]^top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		ans=max(ans,query(id[top[x]],id[x]));
		x=fa[top[x]];
	}
	if(x==y)return ans;
	if(deep[x]>deep[y])swap(x,y);
	return max(ans,query(id[son[x]],id[y]));
}
inline void modify(const int& rt,const int& l,const int& r){
	if(l==r){
		t_min[rt]=t_max[rt]=res;
		return;
	}
	if(lazy[rt])pushdown(rt);
	if(ql<=mid)modify(lson);
	else modify(rson);
	update(rt);
}
inline void tree_modify(const int& to,const int& w){
	ql=id[to];
	res=w;
	modify(1,1,n);
}
inline void Negate(const int& rt,const int& l,const int& r){
	if(ql<=l&&qr>=r){
		ch(rt);
		return;
	}
	if(lazy[rt])pushdown(rt);
	if(ql<=mid)Negate(lson);
	if(qr>mid)Negate(rson);
	update(rt);
}
inline void Negate(const int& l,const int& r){
	ql=l;qr=r;
	Negate(1,1,n);
}
inline void tree_negate(int x,int y){
	while(top[x]^top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		Negate(id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(x==y)return;
	if(deep[x]>deep[y])swap(x,y);
	Negate(id[son[x]],id[y]);
	
}
int main(){
	#define submit
	#ifdef submit
	freopen("maintaintree.in","r",stdin);
	freopen("maintaintree.out","w",stdout);
	#endif
	scanf("%d",&n);
	int a,b,c;
	memset(head,-1,sizeof head);
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c,i);
		add(b,a,c,i);
	}
	deep[1]=1;
	dfs(1);
	dfs(1,1);
	build(1,1,n);
	char str[10];
	while(scanf("%s",str),str[0]!='D'){
		scanf("%d%d",&a,&b);
		if(str[0]=='Q'){
			printf("%d\n",tree_query(a,b));
		}else if(str[0]=='C'){
			tree_modify(change[a],b);
		}else{
			tree_negate(a,b);
		}
	}
	#ifdef submit
	fclose(stdin);
	fclose(stdout);
	#else
	system("pause");
	#endif
}