记录编号	271700	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	2.753 s
提交时间	2016-06-16 10:24:37	内存使用	61.91 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1000010;
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-48;
		ch=getchar();
	}
	return x*f;
}
struct Edge{
	int to,dis,next,num;
}e[maxn];
int head[maxn],tot;
void Add(int u,int v,int w,int x){
	e[++tot].to	=v;
	e[tot].num=x;
	e[tot].next=head[u];
	e[tot].dis=w;
	head[u]=tot;
}
int N;
int fa[maxn], size[maxn], deep[maxn], son[maxn], dis[maxn], edgepos[maxn];
int top[maxn], dfn[maxn], pos[maxn], dfn_cnt;
int maxnum[maxn], minnum[maxn], lazy[maxn], le, ri;

void dfs1(int x){
	size[x] = 1;
	for(int i=head[x]; i; i=e[i].next){
		int to = e[i].to;
		if(size[to]) continue; 
		fa[to] = x; deep[to] = deep[x]+1; dis[to] = e[i].dis;
		edgepos[e[i].num] = to;
		dfs1(to);
		size[x] += size[to];
		if(size[to] > size[son[x]]) son[x] = to;
	}
}
void dfs2(int x, int tp){
	dfn[x] = ++dfn_cnt;
	pos[dfn_cnt] = x;
	top[x] = tp;
	if(son[x]) dfs2(son[x], tp);
	for(int i=head[x]; i; i=e[i].next){
		int to = e[i].to;
		if(!dfn[to]) dfs2(to, to);
	}
}
void updata(int rt){
	if(lazy[rt]!=1) return;
	int lc = rt*2, rc = rt*2+1;
	swap(maxnum[lc], minnum[lc]); maxnum[lc]*=-1; minnum[lc]*=-1; lazy[lc] = !lazy[lc];
	swap(maxnum[rc], minnum[rc]); maxnum[rc]*=-1; minnum[rc]*=-1; lazy[rc] = !lazy[rc];
	lazy[rt] = 0;
}
void build(int rt, int l, int r){
	if(l==r){
		maxnum[rt] = minnum[rt] = dis[pos[l]];
		return;
	}
	int mid = (l+r)>>1, lc = rt*2, rc = rt*2+1;
	build(lc, l, mid); build(rc, mid+1, r);
	maxnum[rt] = max(maxnum[lc], maxnum[rc]);
	minnum[rt] = min(minnum[lc], minnum[rc]);
}
void Setdown(int rt, int l, int r){
	if(le<=l && r<=ri){ 
		swap(maxnum[rt], minnum[rt]);	
		maxnum[rt] *= -1; minnum[rt] *= -1;
		lazy[rt] = !lazy[rt];
		return;
	}
	updata(rt);
	int mid = (l+r)>>1, lc = rt*2, rc = rt*2+1;
	if(le<=mid) Setdown(lc, l, mid);
	if(ri>mid)  Setdown(rc, mid+1, r);
	maxnum[rt] = max(maxnum[lc], maxnum[rc]);
	minnum[rt] = min(minnum[lc], minnum[rc]);
}
int Querymax(int rt, int l, int r){
	if(le<=l&&r<=ri) return maxnum[rt];
	if(lazy[rt]) updata(rt);
	int mid = (l+r)>>1, lc = rt*2, rc = rt*2+1;
	int ans = -0x7f7f7f7f;
	if(le<=mid) ans = max(ans, Querymax(lc, l, mid));
	if(ri>mid) ans = max(ans, Querymax(rc, mid+1, r));
	return ans;
}
void insert(int rt, int l, int r, int p,int c){
	if(l==r){
		maxnum[rt] = minnum[rt] = c;
		return;
	}
	updata(rt);
	int mid = (l+r)>>1, lc = rt*2, rc = rt*2+1;
	if(p<=mid) insert(lc, l, mid, p, c);
	else insert(rc, mid+1, r, p, c);
	maxnum[rt] = max(maxnum[lc], maxnum[rc]);
	minnum[rt] = min(minnum[lc], minnum[rc]);
}
 
void Set(int x, int y){
	while(top[x] != top[y]){
		if(deep[top[x]] < deep[top[y]]) swap(x, y);
		le = dfn[top[x]], ri = dfn[x];
		if(le<=ri) Setdown(1, 1, N);
		x = fa[top[x]]; 
	}
	if(deep[x] > deep[y]) swap(x, y);
	le = dfn[son[x]], ri = dfn[y];
	if(le<=ri) Setdown(1, 1, N);
}
int Query(int x, int y){
	int ans = -0x7f7f7f7f;
	while(top[x] != top[y]){
		if(deep[top[x]] < deep[top[y]]) swap(x, y);
		le = dfn[top[x]], ri = dfn[x];
		if(le<=ri) ans = max(ans, Querymax(1, 1, N));
		x = fa[top[x]]; 
	}
	if(deep[x] > deep[y]) swap(x, y);
	le = dfn[son[x]], ri = dfn[y];
	if(le<=ri) ans = max(ans, Querymax(1, 1, N));
	return ans;
}
int main(){
	
	freopen("maintaintree.in","r",stdin);freopen("maintaintree.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<N;i++){
		int a=read(),b=read(),w=read();
		Add(a,b,w,i);Add(b,a,w,i);
	}
	
	deep[1]=1;dfs1(1);dfs2(1,1);
	build(1,1,N);
	
	string sss;
	while(1){
		cin>>sss;if(sss=="DONE") break;
		int a=read(),b=read();
		if(sss=="QUERY") printf("%d\n",Query(a,b));
		else if(sss=="CHANGE")insert(1,1,N,dfn[edgepos[a]],b);
		else Set(a,b);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}