Description：

一棵 $n$ 个点的有根树。支持如下操作： $M$ $x$ $y$ ：将点 $x$ 的点权改为 $y$ ； $Q$ $x$ ：求以 $x$ 为根的子树的最大连通子块和。

$1\leqslant n\leqslant 200000$

Solution：

肯定是动态 $DP$ ，设 $f[i]$ 表示以 $i$ 为根的子树必须选 $i$ 的最大权联通子块和， $g[i]$ 没有必须选根的限制，转移为： $$ \begin{align} f[k]&=\max(val[k]+\sum_{i\in son[k]}f[i],0)\\ g[k]&=\max(f[k],\max_{i\in son[k]}g[i]) \end{align} $$ 但是要动态修改，树上动态 $DP$ 的经典做法是链分治维护转移矩阵连乘积，但是这题显然不太可做。

但是动态 $DP$ 还是有套路的，就是要定义一个量只与虚儿子有关，然后用线段树维护一整个重链的 $DP$ 转移。

那我们这道题显然要设的就是： $$ \begin{align} f'[k]&=\sum_{i是k的虚儿子}f[i]\\ g'[k]&=\max(f[k],\max_{i是k的虚儿子}g[i]) \end{align} $$ 改写一下转移就是： $$ \begin{align} f[k]&=\max(val[k]+f'[k]+f[son[k]],0)\\ g[k]&=\max(f[k],g'[k],g[son[k]]) \end{align} $$ 然而发现还是不太可做，因为和 $0$ 取 $\max$ 这个操作太奇怪不好维护。

但是这时我们想到洪水那道题，仔细观察上面那个式子，考虑在重链上的选取情况，要么都不选，即选的是子树，要么就是选连续的一段，那么我们就可以用线段树维护最大子段和，然后再和所有虚儿子的值取个 $\max$ ，现在的问题变成了怎么处理 $g$ ，发现如果我们不考虑最后面那一个 $g[son[k]]$ 的话询问就是一个区间最大值，这个也可以用线段树来方便维护，但是要支持删除，所以用一个可删堆就行了， 另一个要注意的是在用虚边更新的时候由于 $f$ 是要求必须选根节点的，所以要用 $state$ 的 $ls$ 来向上更新祖先的 $f$ 值， $g$ 就用最大值更新就好了。

总结一下动态 $DP$ ：

$1$ 、判断题目是动态 $DP$ ，树上问题，有修改点权的操作，可以用一个树形 $DP$ 解决，转移方程一般都不太复杂。

$2$ 、定义一个只与虚儿子有关的量，可以快速修改，并且必须支持撤销贡献（如果是最大值就用个可删堆就可以了），用来维护虚边。

$3$ 、考虑 $DP$ 在实边之间的转移，用线段树维护这个转移，常用的做法有用线段树维护转移矩阵连乘积或者用线段树维护前缀最大值。

$4$ 、修改时就不停向上跳，在虚边的时候特殊处理一下，先删掉他之前的贡献然后加上这次的。

$5$ 、查询时查询它所在重链从他到末尾这一段就是这个子树的答案。

感觉可以理解为以根节点所在的重链为主链，然后在这个主链的基础上 $DP$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline char getc()

{

	register char c = getchar();

	while(c != 'M' && c != 'Q')c = getchar();

	return c;

}

int n,m;

#define MAXN 200010

int val[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int fa[MAXN],siz[MAXN],son[MAXN],dep[MAXN],top[MAXN],bot[MAXN];

int rnk[MAXN],th[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	rnk[k] = ++tot;th[tot] = k;

	top[k] = tp;

	if(son[k] == 0){bot[k] = k;return;}

	dfs2(son[k],tp);bot[k] = bot[son[k]];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

typedef long long ll;

ll f[MAXN],f_[MAXN];

struct heap

{

	priority_queue<ll> ad,dl;

	int siz;

	heap(){siz = 0;}

	void insert(ll k){++siz;ad.push(k);return;}

	void remove(ll k){--siz;dl.push(k);return;}

	ll top()

	{

		if(siz == 0)return 0;

		while(!dl.empty() && ad.top() == dl.top())

		{

			ad.pop();dl.pop();

		}

		return ad.top();

	}

};

heap g[MAXN],g_[MAXN];

bool vis[MAXN];

void dp(int k)

{

	vis[k] = true;

	f[k] = val[k];f_[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dp(e[i].to);

		g[k].insert(g[e[i].to].top());

		if(e[i].to != son[k])g_[k].insert(g[e[i].to].top());

		f[k] += f[e[i].to];

		if(e[i].to != son[k])f_[k] += f[e[i].to];

	}

	f[k] = max(f[k],0ll);

	g[k].insert(f[k]);

	return;

}

struct state

{

	ll s,ms,ls,rs,maxg;

	state(){ls = rs = s = ms = 0;}

	friend state operator + (state a,state b)

	{

		state c;

		c.s = a.s + b.s;

		c.ls = max(a.ls,a.s + b.ls);

		c.rs = max(b.rs,b.s + a.rs);

		c.ms = max(a.rs + b.ls,max(a.ms,b.ms));

		c.maxg = max(a.maxg,b.maxg);

		return c;

	}

};

struct node

{

	int lc,rc;

	state s;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].s.s = f_[th[l]] + val[th[l]];

		t[rt].s.ls = t[rt].s.rs = t[rt].s.ms = max(0ll,f_[th[l]] + val[th[l]]);

		t[rt].s.maxg = g_[th[l]].top();

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].s = t[t[rt].lc].s + t[t[rt].rc].s;

	return;

}

state query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].s;

	if(R <= mid)return query(t[rt].lc,L,R,l,mid);

	if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

	return query(t[rt].lc,L,R,l,mid) + query(t[rt].rc,L,R,mid + 1,r);

}

void maintain(int rt,int p,int l,int r)

{

	if(l == r)

	{

		t[rt].s.s = f_[th[l]] + val[th[l]];

		t[rt].s.ls = t[rt].s.rs = t[rt].s.ms = max(0ll,f_[th[l]] + val[th[l]]);

		t[rt].s.maxg = g_[th[l]].top();

		return;

	}

	if(p <= mid)maintain(t[rt].lc,p,l,mid);

	else maintain(t[rt].rc,p,mid + 1,r);

	t[rt].s = t[t[rt].lc].s + t[t[rt].rc].s;

	return;

}

void modify(int k,ll v)

{

	val[k] = v;

	while(k != 0)

	{

		state res1 = query(root,rnk[top[k]],rnk[bot[k]],1,n);

		maintain(root,rnk[k],1,n);

		state res2 = query(root,rnk[top[k]],rnk[bot[k]],1,n);

		ll x1 = max(res1.ms,res1.maxg);

		ll x2 = max(res2.ms,res2.maxg);

		int anc = fa[top[k]];

		f_[anc] -= res1.ls;f_[anc] += res2.ls;

		g_[anc].remove(x1);

		g_[anc].insert(x2);

		k = anc;

	}

	return;

}

ll query(int k)

{

	state res = query(root,rnk[k],rnk[bot[k]],1,n);

	return max(res.maxg,res.ms);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs1(1,1);dfs2(1,1);

	dp(1);

	build(root,1,n);

	char c;

	for(int i = 1;i <= m;++i)

	{

		c = getc();

		if(c == 'M')

		{

			scanf("%d%d",&a,&b);

			modify(a,(ll)b);

		}

		else

		{

			scanf("%d",&a);

			printf("%lld\n",query(a));

		}

	}

	return 0;

}