This article is made by Jason-Cow.
Welcome to reprint.
But please post the writer's address.
http://www.cnblogs.com/JasonCow/
链剖+线段树
所以为什么 2017.4.8 C题爆零了！！！
我的暴力分呢？
大话西游AC code 假装考试30分拿到了T△T
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
const int maxn=(int)1e5+,maxm=(int)2e5+;
struct edge{int v,next;}e[maxm];
struct cuttochain{int fa,dep,size,son,top;}T[maxn];
int head[maxn],cnt,idx,n,Q,dfn[maxn],Rank[maxn],U[maxn],V[maxn];
long long W[maxn];
void add(int u,int v){e[++cnt]=(edge){v,head[u]},head[u]=cnt;}
void Add(int i){scanf("%d%d",&U[i],&V[i]);add(U[i],V[i]),add(V[i],U[i]);}
void dfs1(int u,int fa){
T[u].fa=fa,T[u].dep=T[fa].dep+,T[u].size=;
for(int i=head[u];i;i=e[i].next){
if(e[i].v!=fa){
dfs1(e[i].v,u);T[u].size+=T[e[i].v].size;
if(T[u].son==||T[e[i].v].size>T[T[u].son].size)T[u].son=e[i].v;
}
}
}
void dfs2(int u,int top){
T[u].top=top,dfn[u]=++idx,Rank[dfn[u]]=u;
if(T[u].son)dfs2(T[u].son,top);
for(int i=head[u];i;i=e[i].next){
if(e[i].v!=T[u].fa && e[i].v!=T[u].son)dfs2(e[i].v,e[i].v);
}
}
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
struct segmenttree{long long max,min,sum;}E[maxn<<];
void up(int x){
E[x].max = max(E[ls].max,E[rs].max);
E[x].min = min(E[ls].min,E[rs].min);
E[x].sum = E[ls].sum+E[rs].sum;
}
void build(int x,int l,int r){
if(l==r){E[x].max=E[x].sum=E[x].min=W[Rank[l]];}
else{build(ls,l,mid),build(rs,mid+,r);up(x);}
}
long long Max(int x,int l,int r,int L,int R){
long long ans=;
if(L<=l&&r<=R)return E[x].max;
else{
if(R<=mid)ans=Max(ls,l,mid,L,R);
else if(L>mid)ans=Max(rs,mid+,r,L,R);
else ans=max( Max(ls,l,mid,L,R) , Max(rs,mid+,r,L,R) );
}
return ans;
}
long long Min(int x,int l,int r,int L,int R){
long long ans=(int)1e8+;
if(L<=l&&r<=R)return E[x].min;
else{
if(R<=mid)ans=Min(ls,l,mid,L,R);
else if(L>mid)ans=Min(rs,mid+,r,L,R);
else ans=min( Min(ls,l,mid,L,R) , Min(rs,mid+,r,L,R) );
}
return ans;
}
long long Sum(int x,int l,int r,int L,int R){
long long ans=;
if(L<=l&&r<=R)return E[x].sum;
else{
if(R<=mid)ans=Sum(ls,l,mid,L,R);
else if(L>mid)ans=Sum(rs,mid+,r,L,R);
else ans=Sum(ls,l,mid,L,R) + Sum(rs,mid+,r,L,R);
}
return ans;
}
void updata(int x,int l,int r,int P,int val){
if(l==r){E[x].max=E[x].sum=E[x].min=val;}
else{
if(P<=mid)updata(ls,l,mid,P,val);
else updata(rs,mid+,r,P,val);
up(x);
}
}
void update(int x,int val){int id=dfn[x];updata(,,n,id,val);}
long long query(int x){
long long MAX1=,MIN1=(int)1e8+;
long long MAX2=,MIN2=(int)1e8+;
if(T[U[x]].dep>T[V[x]].dep){
MAX1=Max(,,n,dfn[U[x]],dfn[U[x]]+T[U[x]].size-);
MIN1=Min(,,n,dfn[U[x]],dfn[U[x]]+T[U[x]].size-);
int LL=,LR=dfn[U[x]]-,RL=dfn[U[x]]+T[U[x]].size,RR=n;
if(LL<=LR){
MAX2=max(MAX2,Max(,,n,LL,LR));
MIN2=min(MIN2,Min(,,n,LL,LR));
}
if(RL<=RR){
MAX2=max(MAX2,Max(,,n,RL,RR));
MIN2=min(MIN2,Min(,,n,RL,RR));
}
}
else{
MAX1=Max(,,n,dfn[V[x]],dfn[V[x]]+T[V[x]].size-);
MIN1=Min(,,n,dfn[V[x]],dfn[V[x]]+T[V[x]].size-);
int LL=,LR=dfn[V[x]]-,RL=dfn[V[x]]+T[V[x]].size,RR=n;
if(LL<=LR){
MAX2=max(MAX2,Max(,,n,LL,LR));
MIN2=min(MIN2,Min(,,n,LL,LR));
}
if(RL<=RR){
MAX2=max(MAX2,Max(,,n,RL,RR));
MIN2=min(MIN2,Min(,,n,RL,RR));
}
}
//cout<<"MAX1="<<MAX1<<endl;cout<<"MIN1="<<MIN1<<endl;cout<<"MAX2="<<MAX2<<endl;cout<<"MIN2="<<MIN2<<endl;
cout<<MAX1*MIN1+MAX2*MIN2<<endl;
return ;
} int main(){
file("a");
scanf("%d%d",&n,&Q);
for(int i=;i<=n;i++)scanf("%lld",&W[i]);
for(int i=;i<n;i++)Add(i);
dfs1(,),dfs2(,),build(,,n);
for(int i=;i<=Q;i++){
char o[];scanf("%s",o+);
if(o[]=='Q'){int x;scanf("%d",&x);query(x);}
else{int id;long long val;scanf("%d%lld",&id,&val);update(id,val);}
}
return ;
}