首先考虑一个暴力的 DP：
设 \(f_u\) 表示以 \(u\) 为根的子树内，要使得 \(u\) 与所有叶子不连通，最小的需要删除的点的点权和。
\[ f_u=\min\left(a_u,\sum\limits_{(u,v)\in E} f_v\right) \]
当 \(u\) 没有儿子时右边那个和式当做 \(\infty\) 处理。
按照套路设一个 \(g_u\) 使得 \[ f_u=\min(a_u,f_{\text{son}_u}+g_u) \]
定义 \(\otimes\) 为把乘法换成加法，加法换成取 \(\min\) 的矩阵乘法。
则 \[
\begin{bmatrix}
g_u&a_u\\
\infty&0
\end{bmatrix}\otimes
\begin{bmatrix}
f_{\text{son}_u} \\
0
\end{bmatrix}=
\begin{bmatrix}
f_u\\
0
\end{bmatrix}
\]
树剖维护一下就 OK 了。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
using namespace std;
const int N = 2e5;
int n,m;
int a[N + 5];
int to[N * 2 + 5],pre[N * 2 + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
struct Matrix
{
long long a[2][2];
inline Matrix()
{
a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0x3f3f3f3f3f3f3f3f;
}
inline Matrix(int)
{
a[0][0] = a[1][1] = 0,a[0][1] = a[1][0] = 0x3f3f3f3f3f3f3f3f;
}
inline Matrix(long long x,long long y)
{
a[0][0] = x,a[0][1] = y,a[1][0] = 0x3f3f3f3f3f3f3f3f,a[1][1] = 0;
}
Matrix operator*(const Matrix &o)
{
Matrix ret;
for(register int i = 0;i < 2;++i)
for(register int j = 0;j < 2;++j)
for(register int k = 0;k < 2;++k)
ret.a[i][j] = min(ret.a[i][j],a[i][k] + o.a[k][j]);
return ret;
}
};
Matrix seg[(N << 2) + 10];
void insert(int x,Matrix k,int p,int tl,int tr)
{
if(tl == tr)
{
seg[p] = k;
return ;
}
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,ls,tl,mid) : insert(x,k,rs,mid + 1,tr);
seg[p] = seg[ls] * seg[rs];
}
Matrix query(int l,int r,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
return seg[p];
int mid = tl + tr >> 1;
Matrix ret(1);
l <= mid && (ret = ret * query(l,r,ls,tl,mid),1);
r > mid && (ret = ret * query(l,r,rs,mid + 1,tr),1);
return ret;
}
int fa[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5],ed[N + 5];
long long f[N + 5],g[N + 5];
void dfs1(int p)
{
sz[p] = 1;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = p,dfs1(to[i]),sz[p] += sz[to[i]];
if(!son[p] || sz[to[i]] > sz[son[p]])
son[p] = to[i];
f[p] += f[to[i]];
}
if(!son[p])
f[p] = a[p];
else
f[p] = min(f[p],(long long)a[p]);
}
void dfs2(int p)
{
static int tot = 0;
id[p] = ++tot;
if(son[p])
top[son[p]] = top[p],dfs2(son[p]),ed[p] = ed[son[p]];
else
ed[p] = id[p],g[p] = 0x3f3f3f3f3f3f3f3f;
for(register int i = first[p];i;i = pre[i])
if(!id[to[i]])
top[to[i]] = to[i],g[p] += f[to[i]],dfs2(to[i]);
}
void update(int x)
{
for(;x;x = fa[x])
{
insert(id[x],Matrix(g[x],a[x]),1,1,n),x = top[x];
Matrix cur = query(id[x],ed[x],1,1,n);
g[fa[x]] -= f[x];
f[x] = min(cur.a[0][0],cur.a[0][1]);
g[fa[x]] += f[x];
}
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
int u,v;
for(register int i = 1;i < n;++i)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
top[1] = 1,dfs1(1),dfs2(1);
for(register int i = 1;i <= n;++i)
insert(id[i],Matrix(g[i],a[i]),1,1,n);
scanf("%d",&m);
char op;
for(;m;--m)
{
scanf(" %c%d",&op,&u);
if(op == 'Q')
{
Matrix ans = query(id[u],ed[u],1,1,n);
printf("%lld\n",min(ans.a[0][0],ans.a[0][1]));
}
else
scanf("%d",&v),a[u] += v,update(u);
}
}