记录编号	306542	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.642 s
提交时间	2016-09-12 16:00:23	内存使用	8.33 MiB

#include "cstdio"
#include "cstring"
#include "iostream"
using namespace std;
typedef long long LL;

const int maxnumber = 100100;
int n, q;
struct Edge
{
	int to, num, next;
}edges[maxnumber<<1];
int head[maxnumber], tot;
int weight[maxnumber];
int point[maxnumber], size[maxnumber], fa[maxnumber], dfn[maxnumber], id[maxnumber], dfsclock;
int Tmin[maxnumber<<2], Tmax[maxnumber<<2];

inline void Read(int& a)
{
	a = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

inline void AddEdge(const int& from, const int& to, const int& num)
{
	edges[++tot].to = to;
	edges[tot].num = num;
	edges[tot].next = head[from];
	head[from] = tot;
}

void Segment_Tree_Build(const int& l, const int& r, const int& rt)
{
	if(l == r){
		Tmax[rt] = Tmin[rt] = weight[id[l]];
		return;
	}
	const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
	Segment_Tree_Build(l, mid, lch);
	Segment_Tree_Build(mid+1, r, rch);
	Tmax[rt] = max(Tmax[lch], Tmax[rch]);
	Tmin[rt] = min(Tmin[lch], Tmin[rch]);
}

int Segment_Tree_Min(const int& l, const int& r, const int& rt, const int& s, const int& t)
{
//	printf("s:%d t:%d\n", s, t);getchar();
	if(s <= l && t >= r) return Tmin[rt];
	const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
	if(t <= mid) return Segment_Tree_Min(l, mid, lch, s, t);
	else if(s >= mid+1) return Segment_Tree_Min(mid+1, r, rch, s, t);
	return min(Segment_Tree_Min(l, mid, lch, s, mid), Segment_Tree_Min(mid+1, r, rch, mid+1, t));
}

int Segment_Tree_Max(const int& l, const int& r, const int& rt, const int& s, const int& t)
{
	if(s <= l && t >= r) return Tmax[rt];
	const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
	if(t <= mid) return Segment_Tree_Max(l, mid, lch, s, t);
	else if(s >= mid+1) return Segment_Tree_Max(mid+1, r, rch, s, t);
	return max(Segment_Tree_Max(l, mid, lch, s, mid), Segment_Tree_Max(mid+1, r, rch, mid+1, t));
}

void Segment_Tree_Change(const int& l, const int& r, const int& rt, const int& pos, const int& w)
{
	if(l == r){
		Tmax[rt] = Tmin[rt] = w;
		return;
	}
	const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
	if(pos <= mid) Segment_Tree_Change(l, mid, lch, pos, w);
	else Segment_Tree_Change(mid+1, r, rch, pos, w);
	Tmax[rt] = max(Tmax[lch], Tmax[rch]);
	Tmin[rt] = min(Tmin[lch], Tmin[rch]);
}

void DFS(const int& a)
{
	size[a] = 1;
	dfn[a] = ++dfsclock;
	id[dfsclock] = a;
	for(int i = head[a]; i; i = edges[i].next){
		int to = edges[i].to, num = edges[i].num;
		if(to == fa[a]) continue;
		point[num] = to;
		fa[to] = a;
		DFS(to);
		size[a] += size[to];
	}
}

int main()
{
	freopen("westward.in", "r", stdin); freopen("westward.out", "w", stdout);
	int from, to;
	char ch[10] = {'\0'};
	Read(n); Read(q);
	for(int i = 1; i <= n; i++) Read(weight[i]);
	for(int i = 1; i < n; i++){
		Read(from); Read(to);
		AddEdge(from, to, i);
		AddEdge(to, from, i);
	}
	
	DFS(1);
//	for(int i = 1; i <= n; i++) printf("dfn[%d]:%d ", i, dfn[i]); puts("");
//	for(int i = 1; i <= n; i++) printf("id[%d]:%d ", i, id[i]); puts("");
	Segment_Tree_Build(1, n, 1);
	
	while(q--){
		scanf("%s", ch);
		if(ch[0] == 'C'){
			int pos, w;
			Read(pos); Read(w);
			Segment_Tree_Change(1, n, 1, dfn[pos], w);
		}
		else{
			int num, s, t;
			Read(num);
			s = dfn[point[num]]; t = s + size[point[num]] - 1;
//			printf("s:%d t:%d\n", s, t);
			int min1, min2, max1, max2;
			min1 = Segment_Tree_Min(1, n, 1, s, t);
			//因为一棵子树上所有的点dfn序都是连续的, 直接区间查询就好了 
			max1 = Segment_Tree_Max(1, n, 1, s, t);
			min2 = Segment_Tree_Min(1, n, 1, 1, s-1);
			max2 = Segment_Tree_Max(1, n, 1, 1, s-1);
			if(t != n){
				min2 = min(min2, Segment_Tree_Min(1, n, 1, t+1, n));
				max2 = max(max2, Segment_Tree_Max(1, n, 1, t+1, n));
			}
//			printf("max1:%d min1:%d max2:%d min2:%d\n", max1, min1, max2, min2);
			printf("%lld\n", (LL)min1*(LL)max1 + (LL)min2*(LL)max2);
		}
	}
	getchar(); getchar();
	fclose(stdin); fclose(stdout);
	return 0;
}
/*
5 3
1 2 3 4 5
1 2
2 3
3 4
4 5
QUERY 1
CHANGE 1 10
QUERY 1
*/