记录编号	98898	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	隨風巽	是否通过	通过
代码语言	C++	运行时间	0.566 s
提交时间	2014-04-25 14:31:43	内存使用	8.95 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<algorithm>
#define INF 200000000
using namespace std;
const int MAXN=100000+10;
typedef long long LL;
struct Edge{int u,v;}edges[MAXN];
int N,Q,total=1,imp[MAXN],temp[MAXN],map[MAXN],x[MAXN],y[MAXN],I,J,P,W;
//map[i]表示原树中的结点i对应的编号
int mino[MAXN*8],maxo[MAXN*8],ansmin,ansmax;
vector<int>g[MAXN];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
void DFS(int v,int par)
{
	int n=g[v].size(),i,u;
	map[v]=total++;
	x[map[v]]=total-1;
	for(i=0;i<n;i++)
	{
		u=g[v][i];
		if(u!=par)DFS(u,v);
	}
	y[map[v]]=total-1;
}
void MAINTAIN(int v,int l,int r)
{
	if(r-l>0)
	{
		int lc=(v<<1),rc=(v<<1|1);
		mino[v]=min(mino[lc],mino[rc]);
		maxo[v]=max(maxo[lc],maxo[rc]);
	}
	else mino[v]=maxo[v]=imp[l];
}
void BUILD(int v,int l,int r)
{
	if(r-l>0)
	{
		int mid=(l+r)>>1;
		BUILD(v<<1,l,mid);
		BUILD(v<<1|1,mid+1,r);
	}
	MAINTAIN(v,l,r);
}
void SET(int v,int l,int r)
{
    if(l==r)imp[P]=W;
	else
	{
		int mid=(l+r)>>1;
		if(P<=mid)SET(v<<1,l,mid);
	    else SET(v<<1|1,mid+1,r);
	}
	MAINTAIN(v,l,r);
}
void QUERY(int v,int l,int r)
{
	if(I<=l&&r<=J)
	{	
		ansmin=min(ansmin,mino[v]);
		ansmax=max(ansmax,maxo[v]);
	}
	else 
	{
		int mid=(l+r)>>1;
		if(I<=mid)QUERY(v<<1,l,mid);
		if(J>=mid+1)QUERY(v<<1|1,mid+1,r);
	}
}
int main()
{
	freopen("westward.in","r",stdin);
	freopen("westward.out","w",stdout);
	scanf("%d%d",&N,&Q);
	int i,e,u,v,t,min1,min2,max1,max2;
	char s[10];
	for(i=1;i<=N;i++)
		scanf("%d",&temp[i]);
	for(i=1;i<=N-1;i++)
	{
		scanf("%d%d",&u,&v);
		g[u].push_back(v);g[v].push_back(u);
		edges[i]=(Edge){u,v};
	}
	DFS(1,-1);
	for(i=1;i<=N;i++)
		imp[map[i]]=temp[i];
	BUILD(1,1,N);
	//for(i=1;i<=N;i++)
	//	cout<<i<<':'<<map[i]<<'('<<x[map[i]]<<','<<y[map[i]]<<')'<<endl;
	for(i=1;i<=Q;i++)
	{	
		scanf("\n%s",&s);
		if(s[0]=='Q')
		{	
			scanf("%d",&e);//u>v
			u=map[edges[e].u];v=map[edges[e].v];
			if(u<v){t=u;u=v;v=t;}
			
			ansmin=INF;ansmax=-INF;
			I=x[u];J=y[u];
			QUERY(1,1,N);
			min1=ansmin;max1=ansmax;
			
			ansmin=INF;ansmax=-INF;
			I=1;J=x[u]-1;
			if(I<=J)QUERY(1,1,N);
			//	cout<<I<<' '<<J<<endl;
			
			I=y[u]+1;J=N;
		    if(I<=J)QUERY(1,1,N);
			min2=ansmin;max2=ansmax;
			//cout<<I<<' '<<J<<endl;
			//cout<<min2<<' '<<max2<<endl;
			
			cout<<LL(min1)*LL(max1)+LL(min2)*LL(max2)<<endl;
		}
		else if(s[0]=='C')
		{	
			scanf("%d%d",&P,&W);
			P=map[P];
			SET(1,1,N);
		}
	}
	return 0;
}