传送门
题意：支持单点修改，维护子树里的最大连通子块和。
思路：
扯皮：
bzojbzojbzoj卡常差评。
网上的题解大多用了跟什么最大子段和一样的转移方法。
但是我们实际上是可以用矩阵转移的传统ddpddpddp写法来做这道题的。
由于我推出来矩阵是3∗33*33∗3的因此常数巨大gggggg了，因此蒟蒻博主只能提供思路和一份TLETLETLE的代码。
正题：
一道考虑链分治+dpdpdp套路题。
同样先考虑静态的版本。
显然可以fi,0/1f_{i,0/1}fi,0/1表示以iii为根的子树,iii在/不在最大子块里是的最大子块和是多少。
然后显然有如下两个转移式：
fp,0=maxv∈son{fv,0,fv,1}f_{p,0}=max_{v\in son}\{f_{v,0},f_{v,1}\}fp,0=maxv∈son{fv,0,fv,1}
fp,1=vali+∑v∈sonmax{fv,1,0}f_{p,1}=val_i+\sum_{v\in son}max\{f_{v,1},0\}fp,1=vali+∑v∈sonmax{fv,1,0}。
现在考虑链分治，我们记一个gi,0/1g_{i,0/1}gi,0/1表示跟以iii为根的子树去掉iii的重儿子所在子树之后,iii在/不在最大子块里时的最大子块和是多少。
考虑推ggg:
gp,0=maxv∈son,v̸=hson{fv,0,fv,1}g_{p,0}=max_{v\in son,v\not=hson}\{f_{v,0},f_{v,1}\}gp,0=maxv∈son,v̸=hson{fv,0,fv,1}
gp,1=fi,1=vali+∑v∈son,v̸=hsonmax{0,fv,1}g_{p,1}=f_{i,1}=val_i+\sum_{v\in son,v\not=hson}max\{0,f_{v,1}\}gp,1=fi,1=vali+∑v∈son,v̸=hsonmax{0,fv,1}
于是就可以用fhsonf_{hson}fhson和gpg_pgp来更新fpf_pfp：
fp,0=max{gp,0,fhson,0,fhson,1}f_{p,0}=max\{g_{p,0},f_{hson,0},f_{hson,1}\}fp,0=max{gp,0,fhson,0,fhson,1}
fp,1=gp,1+valp+max{0,fhson,1}f_{p,1}=g_{p,1}+val_p+max\{0,f_{hson,1}\}fp,1=gp,1+valp+max{0,fhson,1}
那么这个可以用矩阵的形式来表示：
(0fp,0fp,1)=(0−∞−∞gp,000gp,1+valp−∞gp,1+valp)∗(0fhson,0fhson,1)
\left (
\begin{matrix}
0\\
f_{p,0}\\
f_{p,1}\\
\end{matrix}
\right)=
\left (
\begin{matrix}
0&-\infin&-\infin\\
g_{p,0}&0&0\\
g_{p,1}+val_p&-\infin&g_{p,1}+val_p\\
\end{matrix}
\right)*
\left(
\begin{matrix}
0\\
f_{hson,0}\\
f_{hson,1}\\
\end{matrix}
\right)
⎝⎛0fp,0fp,1⎠⎞=⎝⎛0gp,0gp,1+valp−∞0−∞−∞0gp,1+valp⎠⎞∗⎝⎛0fhson,0fhson,1⎠⎞
于是对于每条重链开一棵线段树来维护左边3∗33*33∗3矩阵的转移即可。
代码（被卡常）：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=2e5+5;
const ll inf=1e15;
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(((ans<<2)+ans)<<1)+(ch^48),ch=getchar();
return ~w?ans:-ans;
}
struct deletable_queue{
priority_queue<ll>a,b;
inline void push(const ll&x){a.push(x);}
inline void del(const ll&x){b.push(x);}
inline ll top(){while(b.size()&&a.top()==b.top())a.pop(),b.pop();return a.top();}
}S[N];
int fa[N],top[N],num[N],hson[N],siz[N],dep[N],pred[N],vl[N],bot[N],n,m,tot=0;
ll f[N][2],g[N][2];
vector<int>e[N];
inline ll M(const ll&a,const ll&b){return (a!=-inf)&&(b!=-inf)?a+b:-inf;}
void dfs1(int p){
siz[p]=1;
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p])continue;
fa[v]=p,dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
if(siz[v]>siz[hson[p]])hson[p]=v;
}
}
void dfs2(int p,int tp){
top[p]=tp,pred[num[p]=++tot]=p,bot[tp]=p;
g[p][0]=g[p][1]=f[p][0]=0,f[p][1]=vl[p];
if(!hson[p])return;
dfs2(hson[p],tp);
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p]||v==hson[p])continue;
dfs2(v,v);
S[p].push(max(f[v][0],f[v][1]));
g[p][1]+=max(0ll,f[v][1]);
}
g[p][0]=S[p].top();
f[p][0]=max(g[p][0],max(f[hson[p]][0],f[hson[p]][1]));
f[p][1]=vl[p]+g[p][1]+max(0ll,f[hson[p]][1]);
}
struct Mat{
ll a[3][3];
inline ll*operator[](const int&k){return a[k];}
inline void clear(){for(ri i=0;i<3;++i)for(ri j=0;j<3;++j)a[i][j]=-inf;}
friend inline Mat operator*(Mat A,Mat B){
Mat ret;
ret.clear();
for(ri i=0;i<3;++i)for(ri k=0;k<3;++k)for(ri j=0;j<3;++j)ret[i][j]=max(ret[i][j],M(A[i][k],B[k][j]));
return ret;
}
};
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
struct Node{
int l,r,v;
ll f[2],g[2];
Mat trans;
inline void init(){
trans[0][0]=0,trans[0][1]=-inf,trans[0][2]=-inf;
trans[1][0]=g[0],trans[1][1]=0,trans[1][2]=0;
trans[2][0]=g[1]+v,trans[2][1]=-inf,trans[2][2]=g[1]+v;
}
inline pii val(){return pii(f[0],f[1]);}
}T[N<<2];
inline void Set(int p){
int k=pred[T[p].l];
T[p].f[0]=f[k][0],T[p].f[1]=f[k][1];
T[p].g[0]=g[k][0],T[p].g[1]=g[k][1];
T[p].v=vl[k],T[p].init();
}
inline void pushup(int p){T[p].trans=T[lc].trans*T[rc].trans;}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r)return Set(p);
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void update(int p,int k){
if(T[p].l==T[p].r)return Set(p);
update(k<=mid?lc:rc,k),pushup(p);
}
inline Mat query(int p,int ql,int qr){
if(ql<=T[p].l&&T[p].r<=qr)return T[p].trans;
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,mid)*query(rc,mid+1,qr);
}
inline pii query(int p,int k){
if(T[p].l==T[p].r)return T[p].val();
return query(k<=mid?lc:rc,k);
}
}
inline pii ask(int p){
int bt=bot[top[p]];
if(p==bt)return SGT::query(1,num[p]);
Mat upd=SGT::query(1,num[p],num[bt]-1);
pii val=SGT::query(1,num[bt]),ret;
ret.fi=max(M(upd[1][0],0ll),max(M(upd[1][1],val.fi),M(upd[1][2],val.se)));
ret.se=max(M(upd[2][0],0ll),max(M(upd[2][1],val.fi),M(upd[2][2],val.se)));
return ret;
}
inline void update(int p,int x){
vl[p]=x,f[p][1]=g[p][1]+vl[p]+max(0ll,f[hson[p]][1]);
while(1){
int ft=fa[top[p]],tp=top[p];
if(ft){
pii upd=ask(tp);
S[ft].del(max(upd.fi,upd.se));
g[ft][1]-=max(0ll,upd.se);
}
SGT::update(1,num[p]);
if(ft){
pii upd=ask(tp);
p=ft;
S[p].push(max(upd.fi,upd.se));
g[p][1]+=max(0ll,upd.se);
g[p][0]=S[p].top();
f[p][0]=max(g[p][0],max(f[hson[p]][0],f[hson[p]][1]));
f[p][1]=vl[p]+g[p][1]+max(0ll,f[hson[p]][1]);
}
else break;
}
}
char s[2];
int main(){
n=read(),m=read();
for(ri i=1;i<=n;++i)vl[i]=read(),S[i].push(0ll);
for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
dfs1(1),dfs2(1,1),SGT::build(1,1,n);
for(ri x;m;--m){
scanf("%s",s);
if(s[0]=='M')x=read(),update(x,read());
else{
pii ret=ask(read());
cout<<max(ret.fi,ret.se)<<'\n';
}
}
return 0;
}