记录编号	443118	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.383 s
提交时间	2017-08-29 17:15:49	内存使用	3.08 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#define mid_a ((l+r)>>1)
#define mid_b ((now->l+now->r)>>1)
const int maxn=1e5+5;
using namespace std;
struct edge
{
	int fr,to;
	edge *nt;
	edge(){fr=to=0;nt=NULL;}
}*e[maxn];
struct stree
{
	int l,r;
	long long mx,mi;
	stree *ls,*rs;
	stree(){l=r=mx=mi=0;ls=rs=NULL;}
}*root;
inline int get();
edge* add(int fr,int to);
stree *build(int l,int r);
void dfs(edge* now);
void search(stree *now,int l,int r);
void change(stree *now,int pos,int va);
int n,q;
long long MX,MI;
int N[maxn];
int u[maxn],v[maxn];
int siz[maxn],dfn[maxn],atdfn[maxn],dfsn;
bool jud[maxn];
int main()
{
	freopen("westward.in","r",stdin);
	freopen("westward.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&N[i]);
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u[i],&v[i]);
		e[u[i]]=add(u[i],v[i]);
		e[v[i]]=add(v[i],u[i]);
	}
	dfs(e[1]);
	root=build(1,n);
	for(int i=1;i<=q;i++)
	{
		char c[10];
		scanf("%s",c);
		if(c[0]=='Q')
		{
			long long w,ta,tb,tc,td;
			scanf("%lld",&w);
			if(siz[u[w]]>siz[v[w]])w=v[w];
			else w=u[w];
			MX=0,MI=0x7ffffffffff;
			search(root,dfn[w],dfn[w]+siz[w]-1);
			ta=MX,tb=MI;MX=0,MI=0x7ffffffffff;
			if(dfn[w]-1>=1)search(root,1,dfn[w]-1);
			tc=MX,td=MI;MX=0,MI=0x7ffffffffff;
			if(dfn[w]+siz[w]<=n)search(root,dfn[w]+siz[w],n);
			printf("%lld\n",ta*tb+max(MX,tc)*min(MI,td));
		}
		else
		{
			int s,t;
			scanf("%d%d",&s,&t);
			change(root,dfn[s],t);
		}
	}
	return 0;
}
void change(stree *now,int pos,int va)
{
	if(now->l==now->r){now->mx=now->mi=va;return;}
	else if(pos<=mid_b)change(now->ls,pos,va);
	else change(now->rs,pos,va);
	now->mx=max(now->ls->mx,now->rs->mx);
	now->mi=min(now->ls->mi,now->rs->mi);
}
void search(stree *now,int l,int r)
{
	if(now->l==l&&now->r==r)
	{
		MX=max(MX,now->mx);
		MI=min(MI,now->mi);
	}
	else if(r<=mid_b)search(now->ls,l,r);
	else if(l>mid_b)search(now->rs,l,r);
	else search(now->ls,l,mid_b),search(now->rs,mid_b+1,r);
}
stree *build(int l,int r)
{
	stree *p=new stree();
	p->l=l;p->r=r;
	if(l==r)p->mx=p->mi=N[atdfn[l]];
	else
	{
		p->ls=build(l,mid_a);
		p->rs=build(mid_a+1,r);
		p->mx=max(p->ls->mx,p->rs->mx);
		p->mi=min(p->ls->mi,p->rs->mi);
	}
	return p;
}
void dfs(edge* now)
{
	dfn[now->fr]=++dfsn;
	atdfn[dfsn]=now->fr;
	int fr=now->fr;jud[fr]=true;
	siz[fr]++;
	while(now!=NULL)
	{
		if(!jud[now->to])dfs(e[now->to]),siz[fr]+=siz[now->to];
		now=now->nt;
	}
}
edge* add(int fr,int to)
{
	edge *p=new edge();
	p->fr=fr;p->to=to;
	p->nt=e[fr];
	return p;
}
inline int get()
{
	int t=0,j=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')j=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return j*t;
}