记录编号	99559	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	1.026 s
提交时间	2014-04-28 20:17:10	内存使用	1.59 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 10010
#define M 30100
#define INF 0x3f3f3f3f
struct arr{
	int ff,tt,ww,next;
}c[M];
int X[N],Y[N],Z[N];
struct SEGMENTTREE{
	int l,r,dat;
}t[N << 2];
int n,T;
int r[N];
int root = 0;
int tot = 0;
int fa[N],d[N],top[N],p[N],size[N],son[N];
inline void add(int x,int y){
	c[++tot].ff = x;
	c[tot].tt = y;
	c[tot].next = r[x];
	r[x] = tot;
	return;
}

void build(int p, int l, int r){
	t[p].l = l,t[p].r = r;
	if (l == r){
		t[p].dat = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build(p << 1,l,mid);
	build((p << 1) + 1,mid + 1,r);
	return;
}

void dfs(int x){
	for (int i = r[x]; i; i = c[i].next){
		int y = c[i].tt;
		if (!d[y]){
			d[y] = d[x] + 1;
			fa[y] = x;
			dfs(y);
			size[y]++;
			size[x] += size[y];
			if (size[son[x]] < size[y]) son[x] = y;
		}
	}
	return;
}
int s = 0;
void dfs1(int x,int y){
	p[x] = ++ s;
	top[x] = y;
	if (son[x]) dfs1(son[x],y);
	else return;
	for (int i = r[x]; i; i = c[i].next){
		int y = c[i].tt;
		if (d[y] == d[x] + 1 && y != son[x]){
			dfs1(y,y);
		}
	}
	return;
}


void change(int p,int x,int y){
	if (t[p].l == t[p].r){
		t[p].dat = y;
		return;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	if (x <= mid) change(p << 1,x,y);
	else change((p << 1) + 1,x,y);
	t[p].dat = max(t[p << 1].dat,t[(p << 1) + 1].dat);
	return;
}


int ask_max(int p,int l,int r){
	if (t[p].l >= l && t[p].r <= r){
		return t[p].dat;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	int ans = -INF;
	if (l <= mid) ans = max(ans,ask_max(p << 1,l,r));
	if (r > mid) ans = max(ans,ask_max((p << 1) + 1,l,r));
	return ans;
}

int ask(int x,int y){
	int fx = top[x],fy = top[y];
	int ans = -INF;
	while (fx != fy){
		if (d[fx] < d[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		ans = max(ans,ask_max(1,p[fx],p[x]));
		x = fa[fx]; fx = top[x];
	}
	if (x == y) return ans;
	if (d[x] > d[y]) swap(x,y);
	ans = max(ans,ask_max(1,p[son[x]],p[y]));
	return ans;
}

void change2(int p,int l,int r){
	if (t[p].l == t[p].r){
		t[p].dat *= -1;
		return;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid) change2(p << 1,l,r);
	if (r > mid) change2((p << 1) + 1,l,r);
	t[p].dat = max(t[p << 1].dat,t[(p << 1) + 1].dat);
	return;
}

void NEG(int x,int y){
	int fx = top[x],fy = top[y];
	while (fx != fy){
		if (d[fx] < d[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		change2(1,p[fx],p[x]);
		x = fa[fx]; fx = top[x];
	}
	if (x == y) return;
	if (d[x] > d[y]) swap(x,y);
	change2(1,p[son[x]],p[y]);
	return;
}


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",&X[i],&Y[i],&Z[i]);
		add(X[i],Y[i]);
		add(Y[i],X[i]);
	}
	root = rand() % n + 1;
	size[root] = 1;d[root] = 1;
	dfs(root);
	dfs1(root,root);
	build(1,1,s);
	for (int i = 1; i < n; i++){
		if (d[X[i]] > d[Y[i]]) swap(X[i],Y[i]);
		change(1,p[Y[i]],Z[i]);
	}
	char ch;
	int x,y;
	while (1){
		while (1){
			ch = getchar();
			if (ch == 'Q' || ch == 'C' || ch == 'N' || ch == 'D') break;
		}
		if (ch == 'D') return 0;
		switch (ch){
			case 'Q':{
				while (ch != ' ') ch = getchar();
				scanf("%d%d",&x,&y);
				printf("%d\n",ask(x,y));
				break;
			}
			case 'C':{
				while (ch != ' ') ch = getchar();
				scanf("%d%d",&x,&y);
				change(1,p[Y[x]],y);
				break;
			}
			case 'N':{
				while (ch != ' ') ch = getchar();
				scanf("%d%d",&x,&y);
				NEG(x,y);	
				break;
			}
		}
	}
}