记录编号	144834	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.281 s
提交时间	2014-12-29 22:46:56	内存使用	4.09 MiB

/*====================Asm.Def========================*/
#include <iostream>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
using namespace std;
inline void getd(int &x){
	char c = getchar();bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*======================================================*/
const int maxn = 30005, INF = 0x7fffffff;
int N, Val[maxn];
struct SegT{
	SegT *son[2];
	int L, R, mid, Sum, Max;
	inline void update(){
		Sum = son[0]->Sum + son[1]->Sum;
		Max = max(son[0]->Max, son[1]->Max);
	}
	inline void init(int, int);
	inline void Set(int i, int x){
		if(L == R){Sum = Max = x;return;}
		if(i <= mid)son[0]->Set(i, x);
		else son[1]->Set(i, x);
		update();
	}
	inline int qsum(int l, int r){
		if(l == L && r == R)return Sum;
		if(r <= mid)return son[0]->qsum(l, r);
		if(l > mid)return son[1]->qsum(l, r);
		return son[0]->qsum(l, mid) + son[1]->qsum(mid+1, r);
	}
	inline int qmax(int l, int r){
		if(l == L && r == R)return Max;
		if(r <= mid)return son[0]->qmax(l, r);
		if(l > mid)return son[1]->qmax(l, r);
		return max(son[0]->qmax(l, mid), son[1]->qmax(mid+1, r));
	}
}Seg, Segnode[maxn << 2];
 
inline void SegT::init(int l, int r){
	static int Segptr = 0;
	L = l, R = r, mid = (l + r) >> 1;
	if(L == R){
		Sum = Max = Val[L];
		if(L == 0)Max = -INF;
		son[0] = son[1] = NULL;
		return;
	}
	son[0] = Segnode + Segptr++;son[1] = Segnode + Segptr++;
	son[0]->init(l, mid), son[1]->init(mid+1, r);
	Max = max(son[0]->Max, son[1]->Max);
	Sum = son[0]->Sum + son[1]->Sum;
}
 
struct Node{
	struct Eto{Node *to;Eto *next;Eto(Node *t):to(t){};};
	Eto *adj;
	Node *Son, *pre, *anc;
	int dep, size, val, Loc/*在Seg中的位置*/;
	inline void Addadj(Node *to){Eto *t = new Eto(to);t->next = adj;adj = t;}
	inline void dfs(){
		register Eto *it;
		register Node *t;
		size = 1;
		register int MaxS = 0;
		for(it = adj;it != NULL;it = it->next){
			t = it->to;
			if(t == pre)continue;
			t->pre = this;t->dep = dep + 1;
			t->dfs();
			size += t->size;
			if(t->size > MaxS)Son = t, MaxS = t->size;
		}
	}
	inline void build(){//注意SegT 0位置的Max = -INF
		register Eto *it;
		register Node *t;
		static int iter = 1;
		Loc = iter;
		Val[iter++] = val;
		if(Son == NULL)return;
		Son->anc = anc;
		Son->build();
		for(it = adj;it != NULL;it = it->next){
			t = it->to;
			if(t == pre || t == Son)continue;
			t->anc = t;
			t->build();
		}
	}
}node[maxn];
 
inline void init(){
	getd(N);
	register int i, a, b;
	for(i = 1;i < N;++i){
		getd(a), getd(b);
		node[a].Addadj(node + b);
		node[b].Addadj(node + a);
	}
	for(i = 1;i <= N;++i)
		getd(node[i].val);
	srand(time(NULL));
	register Node *root = node + (rand() % N + 1);
	root->pre = node, root->dep = 1;
	root->dfs();
	root->anc = root;
	root->build();
	Seg.init(1, N);
}
 
inline int Qsum(int a, int b){
	Node *u = node + a, *v = node + b;
	int ans = 0;
	while(u->anc != v->anc){
		if(u->anc->dep < v->anc->dep)swap(u, v);
		ans += Seg.qsum(u->anc->Loc, u->Loc);
		u = u->anc->pre;
	}
	if(u->Loc > v->Loc)swap(u, v);
	ans += Seg.qsum(u->Loc, v->Loc);
	return ans;
}
 
inline int Qmax(int a, int b){
	Node *u = node + a, *v = node + b;
	int ans = -INF;
	while(u->anc != v->anc){
		if(u->anc->dep < v->anc->dep)swap(u, v);
		ans = max(ans, Seg.qmax(u->anc->Loc, u->Loc));
		u = u->anc->pre;
	}
	if(u->dep < v->dep)swap(u, v);
	ans = max(ans, Seg.qmax(v->Loc, u->Loc));
	return ans;
}
 
int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	freopen("output.txt", "w", stdout);
	#else
	freopen("bzoj_1036.in", "r", stdin);
	freopen("bzoj_1036.out", "w", stdout);
	#endif
	
	init();
	register int T, a, b;
	char opt[10], *End;
	getd(T);
	while(T--){
		End = opt;
		while(!isalpha(*End = getchar()));++End;
		while(isalpha(*End = getchar()))++End;
		getd(a), getd(b);
		if(End - opt == 6)//Change
			Seg.Set(node[a].Loc, b);
		else if(opt[1] == 'M')//QMAX
			printf("%d\n", Qmax(a, b));
		else//QSUM
			printf("%d\n", Qsum(a, b));
	}
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}