Description：

给出一棵树，点有点权。多次增加某个点的点权，并在某一棵子树中询问：选出若干个节点，使得每个叶子节点到根节点的路径上至少有一个节点被选择，求选出的点的点权和的最小值。

$1\leqslant n\leqslant 200000$

Solution：

首先如果不考虑修改，那么有朴素的 $DP$ ： $$ f[k]=\max(val[k],\sum_{i\in son[k]}f[i]) $$ 按说树上带修改 $DP$ 应该是用线段树维护矩阵连乘积来做，但是这道题好像不是很好套用这个模型。

观察一下这个 $DP$ 的性质，会发现随便拿出来一条链，一定是前半部分用第二种转移，最后一个点用第一种转移。

那么我们就可以给这棵树轻重链剖分，用线段树维护每个位置截止的值，另开一个数组 $g$ 表示所有轻儿子的 $f$ 值之和，那么如果某个点的 $f$ 值变化，那么有一个后缀线段树要维护的东西都会变化，在查询时就需要查询从这个点到链底的最大值即可。

用了一种非常有趣的方式来巧妙地维护了前缀和，从而使得线段树只要单点修改就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline char getc()

{

	register char c = getchar();

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

	return c;

}

int n,m;

#define MAXN 200010

typedef long long ll;

ll 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],dep[MAXN],siz[MAXN],son[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)

{

	top[k] = tp;

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

	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;

}

ll f[MAXN],g[MAXN];

bool vis[MAXN];

void dp(int k)

{

	vis[k] = true;

	g[k] = 0;

	if(son[k] == 0)

	{

		f[k] = g[k] = val[k];

		return;

	}

	ll sum = 0;

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

	{

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

		dp(e[i].to);

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

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

	}

	f[k] = min(sum,val[k]);

	return;

}

struct state

{

	ll minv,sum;

	state(){minv = sum = 0;}

	friend state operator + (state a,state b)

	{

		state res;

		res.sum = a.sum + b.sum;

		res.minv = min(a.minv,a.sum + b.minv);

		return res;

	}

};

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.sum = g[th[l]];

		t[rt].s.minv = val[th[l]];

		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;

}

void add(int rt,int p,ll k,int l,int r)

{

	if(l == r)

	{

		t[rt].s.sum += k;

		t[rt].s.minv = val[th[l]];

		return;

	}

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

	else add(t[rt].rc,p,k,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 modify(int k,ll v)

{

	val[k] += v;v = 0;

	int st = k;

	while(k != 0)

	{

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

		add(root,rnk[k],v,1,n);

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

		v = res2 - res1;

		k = fa[top[k]];

	}

	return;

}

ll query(int k)

{

	return query(root,rnk[k],rnk[bot[k]],1,n).minv;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lld",&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);

	scanf("%d",&m);

	char c;

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

	{

		c = getc(); 

		if(c == 'C')

		{

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

			modify(a,(ll)b);

		}

		else

		{

			scanf("%d",&a);

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

		}

	}

	return 0;

}