题目分析：
解决了上次提到的《切树游戏》后，这道题就是一道模板题。
注意我们需要用堆维护子重链的最大值。这样不会使得复杂度变坏，因为每个重链我们只考虑一个点。
时间复杂度$O(nlog^2n)$
代码：
#include<bits/stdc++.h>
using namespace std; typedef long long ll; const int maxn = ; int n,m;
int v[maxn];
vector<int> g[maxn];
int fa[maxn],dep[maxn],sz[maxn],son[maxn],top[maxn],tail[maxn];
int where[maxn],number[maxn],num;
ll TOT[maxn]; struct Priority_queue{
priority_queue <ll,vector<ll>,less<ll> > pq,del;
void Insert(ll now){pq.push(now);}
void Erase(ll now){del.push(now);}
ll Top(){
while(!del.empty()&&pq.top() == del.top()) pq.pop(),del.pop();
return pq.top();
}
int Size(){return pq.size()-del.size();}
}PQ[maxn]; struct node{ll L,R,D,C;}T[maxn<<]; void push_up(int now){
T[now].L = max(T[now<<].L,T[now<<].C+T[now<<|].L);
T[now].R = max(T[now<<|].R,T[now<<|].C+T[now<<].R);
T[now].D = max(max(T[now<<].D,T[now<<|].D),T[now<<].R+T[now<<|].L);
T[now].C = T[now<<].C+T[now<<|].C;
} node merge(node alpha,node beta){
node gamma; gamma.L = max(alpha.L,alpha.C+beta.L);
gamma.R = max(beta.R,beta.C+alpha.R);
gamma.D = max(max(alpha.D,beta.D),alpha.R+beta.L);
gamma.C = alpha.C+beta.C;
return gamma;
} char readchar(){
char ch = getchar(); while(ch != 'M' && ch != 'Q') ch = getchar();
return ch;
} void read(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&v[i]);
for(int i=;i<n;i++){
int x,y; scanf("%d%d",&x,&y);
g[x].push_back(y); g[y].push_back(x);
}
} void dfs1(int now,int f,int dp){
fa[now] = f; dep[now] = dp;
for(int i=;i<g[now].size();i++){
if(g[now][i] == f) continue;
dfs1(g[now][i],now,dp+);
sz[now] += sz[g[now][i]];
if(son[now]==||sz[son[now]]<sz[g[now][i]])son[now]=g[now][i];
}
sz[now]++;
if(son[now]) tail[now] = tail[son[now]];
else tail[now] = now;
} void dfs2(int now,int tp){
top[now] = tp;number[now] = ++num; where[num] = now;
if(son[now]) dfs2(son[now],tp);
for(int i=;i<g[now].size();i++){
if(g[now][i] == fa[now] || g[now][i] == son[now]) continue;
dfs2(g[now][i],g[now][i]);
}
} void Modify(int now,int tl,int tr,int place){
if(tl == tr){
tl = where[tl];
T[now].C = TOT[tl] + v[tl];
T[now].L = max(0ll,TOT[tl]+v[tl]); T[now].R = T[now].L;
if(PQ[tl].Size()) T[now].D = max(PQ[tl].Top(),T[now].L);
else T[now].D = T[now].L;
}else{
int mid = (tl+tr)/;
if(place <= mid) Modify(now<<,tl,mid,place);
else Modify(now<<|,mid+,tr,place);
push_up(now);
}
} node Query(int now,int tl,int tr,int l,int r){
if(tl >= l && tr <= r) return T[now];
int mid = (tl+tr)/;
if(r <= mid) return Query(now<<,tl,mid,l,r);
if(l > mid) return Query(now<<|,mid+,tr,l,r);
return merge(Query(now<<,tl,mid,l,r),Query(now<<|,mid+,tr,l,r));
} void dfs3(int now){
if(son[now]) dfs3(son[now]);
for(int i=;i<g[now].size();i++){
int mp = g[now][i];
if(mp == fa[now] || mp == son[now]) continue;
dfs3(mp);
PQ[now].Insert(Query(,,n,number[mp],number[tail[mp]]).D);
}
Modify(,,n,number[now]);
if(top[now] == now){
long long data = Query(,,n,number[now],number[tail[now]]).L;
if(data > && fa[now]) TOT[fa[now]]+=data;
}
} void work(){
dfs1(,,);
dfs2(,);
dfs3();
for(int i=;i<=m;i++){
char ch = readchar();
if(ch == 'M'){
int x,y; scanf("%d%d",&x,&y);
stack<int> sta; int now = top[x];
while(fa[now]) sta.push(now),now = top[fa[now]];
while(!sta.empty()){
int mp = sta.top();sta.pop();
node res = Query(,,n,number[mp],number[tail[mp]]);
PQ[fa[mp]].Erase(res.D);
if(res.L > ) TOT[fa[mp]]-=res.L;
Modify(,,n,number[fa[mp]]);
}
now = x; v[x] = y;
while(now){
Modify(,,n,number[now]);
now = top[now];
node res = Query(,,n,number[now],number[tail[now]]);
if(res.L > && fa[now]) TOT[fa[now]]+=res.L;
PQ[fa[now]].Insert(res.D);
now= fa[now];
}
}else{
int x; scanf("%d",&x);
long long ans = Query(,,n,number[x],number[tail[x]]).D;
printf("%lld\n",ans);
}
}
} int main(){
read();
work();
return ;
}