记录编号	98895	评测结果	AAWWWTTT
题目名称	大话西游	最终得分	25
用户昵称	超级傲娇的AC酱	是否通过	未通过
代码语言	C++	运行时间	3.349 s
提交时间	2014-04-25 14:07:02	内存使用	1.07 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
struct Ans{long long Max,Min;};
struct Node{long long val;vector<Node*>End;};
struct Edge{Node *st,*en;};
Node* V[100001];Edge* E[100001];long long N,Q;
void Build();
long long Query(long long);
void Change(long long,long long);
Ans dfs(Node *,Node *);
int main()
{
	freopen("westward.in","r",stdin);
	freopen("westward.out","w",stdout);
	ios::sync_with_stdio(false);
	string s;long long e,pos,num,i;
	Build();
	for(i=0;i<Q;i++){
		cin>>s;
		if(s[0]=='Q'){
			cin>>e;
			cout<<Query(e)<<endl;
		}
		if(s[0]=='C'){
			cin>>pos>>num;
			Change(pos,num);
		}
	}
	return 0;
}
void Build()
{
	long long i,x,u,v;
	cin>>N>>Q;
	for(i=1;i<=N;i++)
	{
		V[i]=new Node;
		cin>>V[i]->val;
	}
	for(i=1;i<=N-1;i++)
	{
		E[i]=new Edge;
		cin>>u>>v;
		V[u]->End.push_back(V[v]);
		V[v]->End.push_back(V[u]);
		E[i]->st=V[u];
		E[i]->en=V[v];
	}
}
void Change(long long pos,long long num)
{
	V[pos]->val=num;
}
long long Query(long long e)
{
	Ans Part1,Part2;
	Part1=dfs(E[e]->st,E[e]->en);
	Part2=dfs(E[e]->en,E[e]->st);
	return Part1.Min*Part1.Max+Part2.Min*Part2.Max;
}
Ans dfs(Node *pos,Node *UnGo)
{
	Ans R;long long i;R.Max=R.Min=pos->val;
	if(pos->End.size()==0)
		return R;
	else
	{
		for(i=0;i<pos->End.size();i++)
		{
			if(pos->End[i]!=UnGo)
			{
				R=dfs(pos->End[i],pos);
				R.Max=max(pos->val,R.Max);
				R.Min=min(pos->val,R.Min);
			}
		}
		return R;
	}
}