记录编号	437338	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.767 s
提交时间	2017-08-14 08:21:55	内存使用	1.03 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=10000+100;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int n,num,cnt;
int head[2*M],size[M],dep[M],son[M],fa[M],v[M];
int top[M],id[M],pos[M],mx[4*M],mn[4*M],adda[4*M];
struct DATE{int fr,to,w,last;}date[2*M];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void add(int x,int y,int z){
	date[++num]=(DATE){x,y,z,head[x]};
	head[x]=num;
}
void dfs1(int x){
	size[x]=1;son[x]=0;
	for(int i=head[x];i;i=date[i].last){
		int to=date[i].to;
		if(to!=fa[x]){
			fa[to]=x;v[to]=date[i].w;
			dep[to]=dep[x]+1;dfs1(to);
			size[x]+=size[to];
			if(size[to]>size[son[x]]) son[x]=to;
		}
	}
}
void dfs2(int x,int tp){
	top[x]=tp;
	id[x]=++cnt;pos[cnt]=x;
	if(son[x]) dfs2(son[x],tp);
	for(int i=head[x];i;i=date[i].last){
		int to=date[i].to;
		if(to!=fa[x]&&to!=son[x])
			dfs2(to,to);
	}
}
inline void pushup(int rt){
	mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
	mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
inline void pushdown(int rt){
	if(adda[rt]){
		adda[rt]=0;
		int ls=rt<<1,rs=rt<<1|1;
		int mnn=mn[ls];
		mn[ls]=mx[ls]*-1;mx[ls]=mnn*-1;adda[ls]^=1;
		mnn=mn[rs];
		mn[rs]=mx[rs]*-1;mx[rs]=mnn*-1;adda[rs]^=1;
	}
}
void bt(int rt,int l,int r){
	if(l==r){
		mn[rt]=mx[rt]=v[pos[l]];
		return ;
	}
	int mid=l+r>>1;
	bt(lson);bt(rson);
	pushup(rt);
}
int query(int s,int t,int rt,int l,int r){
	if(s<=l&&r<=t) return mx[rt];
	pushdown(rt);
	int mid=l+r>>1;int res=1<<31;
	if(s<=mid) res=max(res,query(s,t,lson));
	if(t>mid) res=max(res,query(s,t,rson));
	return res;
}
void change(int pos,int zhi,int rt,int l,int r){
	if(l==r) {mx[rt]=mn[rt]=zhi;return ;}
	pushdown(rt); int mid=l+r>>1;
	if(pos<=mid) change(pos,zhi,lson);
	else change(pos,zhi,rson);
	pushup(rt);
}
void neg(int s,int t,int rt,int l,int r){
	//if(s>t) return ;
	if(s<=l&&r<=t){
		int mnn=mn[rt];
		mn[rt]=mx[rt]*(-1);mx[rt]=mnn*(-1);
		adda[rt]^=1;return ;
	}
	pushdown(rt); int mid=l+r>>1;
	if(s<=mid) neg(s,t,lson);
	if(t>mid) neg(s,t,rson);
	pushup(rt);
}
inline int Query(int x,int y){
	int fx=top[x],fy=top[y];int res=1<<31;
	while(fx!=fy){
		if(dep[fx]<dep[fy])
			swap(x,y),swap(fx,fy);
		res=max(res,query(id[fx],id[x],1,1,n));
		x=fa[fx];fx=top[x];
	}
	//if(dep[x]==dep[y]) return res;
	if(dep[x]>dep[y]) swap(x,y);
	res=max(res,query(id[son[x]],id[y],1,1,n));
	return res;
}
inline void Neg(int x,int y){
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(dep[fx]<dep[fy])
			swap(x,y),swap(fx,fy);
		neg(id[fx],id[x],1,1,n);
		x=fa[fx];fx=top[x];
	}
	//if(dep[x]==dep[y]) return ;
	if(dep[x]>dep[y]) swap(x,y);
	neg(id[son[x]],id[y],1,1,n);
}
int DK(){
	freopen("maintaintree.in","r",stdin);
	freopen("maintaintree.out","w",stdout);
	n=read();int aa,bb,cc;char s[10];
	for(int i=1;i<n;i++){
		aa=read();bb=read();cc=read();
		add(aa,bb,cc);add(bb,aa,cc);
	}
	dep[1]=1;dfs1(1);dfs2(1,1);bt(1,1,n);
	while(1){
		scanf("%s",s);
		if(s[0]=='D') break;
		aa=read();bb=read();
		if(s[0]=='Q') {printf("%d\n",Query(aa,bb));continue;}
		if(s[0]=='C'){
			int fr=date[2*aa-1].fr,to=date[2*aa-1].to;
			if(fa[fr]==to) change(id[fr],bb,1,1,n);
			else change(id[to],bb,1,1,n);   continue;
		}
		Neg(aa,bb);
	}
	return 0;
}
int dk=DK();
int main(){
	;
}