请先完成 ddp模板
一个 ddp 讲解视频
Part0：题意解释
感觉题面太阴间了。所以解释一下：
C x t 表示把 \(x\) 结点的权值改为 \(t\).
Q x ：把 \(x\) 子树中一些结点删去，使得 \(x\) 与 \(x\) 子树内所有叶子结点不连通。求 删去的结点权值和 的最小值。
Part1：先不考虑修改操作
发现原题变成了一道简单的树形dp问题
令 \(f_u\) 表示 使 \(u\) 与其子树内叶子节点都不连通的最小代价。\(val_u\) 是 \(u\) 的权值
容易得到 \(f_u=\min(val_u,\sum \limits_{v \in son_u} f_v)\)
叶子节点特判：\(f_u=val_u\)
这样每一次修改操作后重新更新 \(f_u\) 的时间复杂度是 \(O(nm)\).
Part3：ddp
注意到，每一次修改某一个结点 \(x\) 的 \(val_x\) 时，\(f_u\) 会被修改的 \(u\) 只有 \(x\) 到根节点这一条链上的结点。所以就可以考虑ddp了。
根据ddp的套路，考虑把重儿子和轻儿子拆开。
令 \(s_u\) 为 \(u\)的重儿子。令 \(g_u= \sum \limits_{v \in son_u,v\neq s_u} f_v\).
现在重新写出 \(f\) 的转移方程：\(g_u=\min(val_u,g_u+f_{s_u})\)
根据ddp的套路，现在考虑把原方程转化成矩阵的形式。
先对矩阵乘法做一点改变：令 \(C_{i,j}=\min \limits_k (A_{i,k}+B_{k,j})\)
简单变一下原来的 \(f\) 转移式子：\(g_u=\min(val_u+0,g_u+f_{s_u})\)
可以得到
\[ \begin{bmatrix} g_u & val_u\\0 & \infty \end{bmatrix} * \begin{bmatrix} f_{s_u}\\0 \end{bmatrix} = \begin{bmatrix} f_u\\0 \end{bmatrix} \]所以，每个结点对应的转移矩阵就是 \(\begin{bmatrix}g_u & val_u\\0 & \infty \end{bmatrix}\).
要求一个点 \(u\) 的 \(f_u\) 时，就只用求 \(dfn_u\) 到 \(ed_u\) 的矩阵乘积。
要修改一个点 \(u\) 的 \(val_u\) 时，在线段树中修改 \(u\) 对应的矩阵，然后求出 \(f_{top_u}\) 的变化值，并修改 \({fa_{top_u}}\) 对应的矩阵。将 \(u\) 赋值为 \({fa_{top_u}}\)，再次重复运算，直到到达根节点。
这里有一些注意点：
- 为什么要把 \(f_u\) 表示成 \(\begin{bmatrix}f_u\\0 \end{bmatrix}\)，而不是 表示成 \(\begin{bmatrix}f_u&0 \end{bmatrix}\) 呢？因为第一种表示方式，是用 \(\begin{bmatrix}f_{s_u}\\0 \end{bmatrix}\)左乘转移矩阵 \(\begin{bmatrix}g_u & val_u\\0 & \infty \end{bmatrix}\) 。而在 dfn 标号中， \(dfn_u=dfn_{s_u}-1\) 。第二种表示方式，是右乘转移矩阵，不方便线段树的维护。ps：模板题中的题解也提到了这个tip。
- 叶子结点的矩阵要特殊处理，正常的结点对应的矩阵就是 \(\begin{bmatrix}g_u & val_u\\0 & \infty \end{bmatrix}\) 。但是叶子结点的矩阵要对应成 \(\begin{bmatrix}f_u\\0 \end{bmatrix}\)。可以自行思考一下为什么。
Part4：代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
int read(){
int x=0;char c=getchar();bool f=0;
while(c>'9'||c<'0'){f|=(c=='-');c=getchar();}
while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return f?-x:x;
}
void write(ll x){
if(x<0) putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
struct Matrix{
ll mat[2][2];
Matrix(){memset(mat,0x3f,sizeof(mat));}
Matrix operator *(Matrix b){
Matrix c;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
c.mat[i][j]=min(c.mat[i][j],mat[i][k]+b.mat[k][j]);
}
}
}
return c;
}
}v[MAXN<<2];
int n;
ll val[MAXN];
vector<int> G[MAXN];
int fa[MAXN],dfn[MAXN],idfn[MAXN],siz[MAXN],son[MAXN],ed[MAXN],top[MAXN];
Matrix g[MAXN];
ll f[MAXN];
void dfs0(int u){
siz[u]=1,son[u]=0;
for(int v:G[u]){
if(v==fa[u]) continue;
fa[v]=u;
dfs0(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs1(int u,int tp){
dfn[u]=++dfn[0];
idfn[dfn[0]]=u;
top[u]=tp;
ed[tp]=max(ed[tp],dfn[u]);
if(!son[u]){//特判叶子结点 叶子节点的g=f
f[u]=val[u];
g[u].mat[0][0]=val[u];
g[u].mat[1][0]=0;
return;
}
f[u]=0;
g[u].mat[0][0]=0;
g[u].mat[0][1]=val[u];
g[u].mat[1][1]=0;
if(son[u]){
dfs1(son[u],tp);
f[u]+=f[son[u]];
}
for(int v:G[u]){
if(v==fa[u]||v==son[u]) continue;
dfs1(v,v);
f[u]+=f[v];
g[u].mat[0][0]+=f[v];
}
f[u]=min(f[u],val[u]);
}
#define lc (u<<1)
#define rc (u<<1|1)
void build(int u,int l,int r){
if(l==r){v[u]=g[idfn[l]];return;}
int mid=l+r>>1;
build(lc,l,mid),build(rc,mid+1,r);
v[u]=v[lc]*v[rc];
}
void change(int u,int l,int r,int pos){
if(l==r){v[u]=g[idfn[l]];return;}
int mid=l+r>>1;
if(pos<=mid) change(lc,l,mid,pos);
else change(rc,mid+1,r,pos);
v[u]=v[lc]*v[rc];
}
Matrix query(int u,int l,int r,int L,int R){
if(l>=L&&r<=R) return v[u];
int mid=l+r>>1;
if(R<=mid) return query(lc,l,mid,L,R);
else if(L>mid) return query(rc,mid+1,r,L,R);
else return query(lc,l,mid,L,R)*query(rc,mid+1,r,L,R);
}
void work1(int u,ll Val){
if(son[u]) g[u].mat[0][1]+=Val;
else g[u].mat[0][0]+=Val;
val[u]+=Val;
while(u){
int tp=top[u];
Matrix las=query(1,1,n,dfn[tp],ed[tp]);
change(1,1,n,dfn[u]);
Matrix now=query(1,1,n,dfn[tp],ed[tp]);
if(!fa[tp]) break;
g[fa[tp]].mat[0][0]+=now.mat[0][0]-las.mat[0][0];
u=fa[tp];
}
}
ll work2(int u){
Matrix ret=query(1,1,n,dfn[u],ed[top[u]]);
return ret.mat[0][0];
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read();
for(int i=1;i<=n;i++) val[i]=1ll*read();
for(int i=1;i<n;i++){
int u=read(),v=read();
G[u].push_back(v),G[v].push_back(u);
}
dfs0(1),dfs1(1,1);build(1,1,n);
int Q=read();
while(Q--){
int x,t;
char op;scanf("\n%c %d",&op,&x);
if(op=='C'){scanf("%d",&t);work1(x,1ll*t);}
else write(work2(x)),putchar('\n');
}
return 0;
}