似乎 NOIP2019D2T3 把这个东西宣传的很到位啊。
我才不会告诉你我已经学过一遍了 早就忘了。
以 bzoj4712 洪水 为例。
首先我们有一个暴力 DP 的式子。
令 (dp[x]) 表示以 (x)为根的子树的最小代价，(v[x]) 表示每个点的权值。
于是转移就是：
不用动态 DP 的做法
实际上这道题有一个不用动态 DP 的做法。
不想看的可以直接跳过。
[戳我跳过](#动态 DP)
因为保证了所有的 (to) 都是非负数，那么也就是说，所有的 (v[x]) 都是只增不减的，那么也就意味着，所有的 (dp[x]) 也是只增不减的。
那么，每个点之多发生一次 (sumlimits_{yin child_x} dp[y]) 由 (leq v[x]) 变成 (> v[x])（被修改的那个点除外）。
于是这种情况也是最多发生 (n+m) 次的。加上 (m) 是因为每一次修改会有可能破坏一次。
所以如果我们可以得到一种很好的想法：找到所有的 (sumlimits_{yin child_x} dp[y]) 与 (v[x]) 的大小关系发生改变的点，然后暴力修改。
可以发现，从被修改的点的 (dp) 值被增加的量开始，其所有的祖先，最下面会有一段和这个增量相同。直到某一个点的 (sumlimits_{yin child_x} dp[y]) 与 (v[x]) 的大小关系发生改变，或者到 (sumlimits_{yin child_x} dp[y] geq v[x]) 停止。所以我们要做的就是通过数据结构维护最近的一次 (sumlimits_{yin child_x} dp[y]) 与 (v[x]) 的大小关系发生改变的情况。
可以直接维护每个点的 (v[x] - sumlimits_{yin child_x} dp[y]) 的结果，然后进行树链剖分， 在重链上可以直接进行线段树二分找出这样的点。
于是整个题目可以在总 (O((n+m)log^2 n)) 的复杂度完成。
问题
某毒瘤：“听说你可以用均摊分析的方法过掉？”
然后轻轻的敲下了 vim problem.tex，然后找到 n<=200000，保证任意to都为非负数 这一行，将光标停在了那个逗号上，优雅地按下了可怕的 d$，那句“保证任意to都为非负数”瞬间消失得无影无踪。
动态 DP
如上文所述，如果不能保证 (to) 为非负数，那么我们之前的均摊分析就不成立，复杂度就直接炸没影了。
我们考虑使用一种叫作动态 DP 的科技来解决这个问题。
我们回顾一下上面的 DP 式子：
如果我们把这棵树进行树链剖分的话，我们先定义一些方便的符号：(child_x) 表示 (x) 的所有孩子的集合；(son_x) 表示 (x) 的重儿子（这个名字怎么充满的封建的味道），(light_x) 表示 (x) 的轻儿子集合。
那么，如果我们令 (h[x]) 表示 (x) 的所有轻儿子的 (dp) 值之和，即 (h[x] = sumlimits_{yin light_x} dp[y])。则原式可以改写为：
类似于一般的递推，我们考虑用一种新式的矩阵来表示这种关系：
对于两个矩阵 (A) 和 (B)，定义一种新的乘法运算，令 (C = A imes B)，则
那么，我们上面的运算可以被用矩阵乘法的形式表示为：
类似于矩阵快速幂，我们来证明一下我们定义的这一种矩乘具有结合律。
对于矩阵大小为 (a imes b) 的矩阵 (A)，大小为 (b imes c) 的矩阵 (B)，大小为 (c imes d) 的矩阵 (C)，求证：((A imes B) imes C = A imes (B imes C))。
证明：
令 (E = A imes B)，(F = B imes C)。
则
[E_{i, j} = min_{k=1}^b A_{i, k} + B_{k, j}\ F_{i, j} = min_{k=1}^c B_{i, k} + C_{k, j} ]然后
[E imes C = min_{l=1}^c{min_{k=1}^b A_{i, k} + B_{k, l} + C_{l,j}}\ egin{align*} A imes F &= min_{l=1}^b{A_{i,l} + min_{k=1}^c B_{i, k} + C_{k, j}}\ &= min_{k=1}^c{min_{l=1}^b A_{i, l} + B_{i, k} + C_{k, j}}\ &= min_{l=1}^c{min_{k=1}^b A_{i, k} + B_{i, l} + C_{l, j}}\ end{align*} ]容易发现 (E imes C = A imes F)，即 ((A imes B) imes C = A imes (B imes C))。
令 (V_x = egin{bmatrix}h[x]&v[x]\0&0 end{bmatrix})。
我们可以发现，如果我们把一条重链上面的点的 (V) 矩阵从某一个点 (x) 开始，按照深度从上到下的顺序乘在一起，最后再乘上一个 (egin{bmatrix}0\0end{bmatrix})，那么我们就可以得到重链顶端的 (x) 的 (dp) 值了。
上面就是查询的方法了。
下面我们考虑修改应该怎么做。
修改会影响到的 (dp) 值是从根到 (x) 的所有点的。——但是我们实际上不需要考虑所有的 (dp) 值，因为 (dp) 值本身没有被存储下来。需要考虑的是影响到了哪些 (h[x])。
每一个点的重儿子的 (dp) 值不影响 (h[x]) 值，被影响的只有每一条重链之间的那一个轻边。所以直接在树剖向上跳的时候用新的 (dp) 值更新一下就好了。
然后这样的时间复杂度就是一个树链剖分的复杂度 (O(qlog^2n))。
代码如下：
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
#define lc o << 1
#define rc o << 1 | 1
const int N = 200000 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, dfc;
int a[N];
int dep[N], f[N], siz[N], son[N], dfn[N], pre[N], top[N], bot[N];
ll dp[N], h[N];
struct Edge { int to, ne; } g[N << 1]; int head[N], tot;
inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }
inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }
struct Matrix {
ll a[2][2];
inline Matrix() { memset(a, 0, sizeof(a)); }
inline Matrix operator * (const Matrix &b) {
Matrix c;
c.a[0][0] = std::min(a[0][0] + b.a[0][0], a[0][1] + b.a[1][0]);
c.a[0][1] = std::min(a[0][0] + b.a[0][1], a[0][1] + b.a[1][1]);
c.a[1][0] = std::min(a[1][0] + b.a[0][0], a[1][1] + b.a[1][0]);
c.a[1][1] = std::min(a[1][0] + b.a[0][1], a[1][1] + b.a[1][1]);
return c;
}
} v[N], t[N << 2];
inline void dfs1(int x, int fa = 0) {
dep[x] = dep[fa] + 1, f[x] = fa, siz[x] = 1;
for fec(i, x, y) if (y != fa) dfs1(y, x), siz[x] += siz[y], siz[y] > siz[son[x]] && (son[x] = y);
}
inline void dfs2(int x, int pa) {
top[x] = pa, dfn[x] = ++dfc, pre[dfc] = x;
if (!son[x]) return (void)(bot[x] = x);
dfs2(son[x], pa), bot[x] = bot[son[x]];
for fec(i, x, y) if (y != f[x] && y != son[x]) dfs2(y, y);
}
inline void dfs3(int x, int fa = 0) {
for fec(i, x, y) if (y != fa) {
dfs3(y, x);
dp[x] += dp[y];
if (y != son[x]) h[x] += dp[y];
}
if (!son[x]) dp[x] = h[x] = INF;
smin(dp[x], a[x]);
}
inline void build(int o, int L, int R) {
if (L == R) return t[o].a[0][0] = h[pre[L]], t[o].a[0][1] = a[pre[L]], (void)0;
int M = (L + R) >> 1;
build(lc, L, M), build(rc, M + 1, R);
t[o] = t[lc] * t[rc];
}
inline void qadd(int o, int L, int R, int x) {
if (L == R) return t[o].a[0][0] = h[pre[L]], t[o].a[0][1] = a[pre[L]], (void)0;
int M = (L + R) >> 1;
if (x <= M) qadd(lc, L, M, x);
else qadd(rc, M + 1, R, x);
t[o] = t[lc] * t[rc];
}
inline Matrix qsum(int o, int L, int R, int l, int r) {
if (l <= L && R <= r) return t[o];
int M = (L + R) >> 1;
if (r <= M) return qsum(lc, L, M, l, r);
if (l > M) return qsum(rc, M + 1, R, l, r);
return qsum(lc, L, M, l, r) * qsum(rc, M + 1, R, l, r);
}
inline ll qry(int x) {
const Matrix &tmp = qsum(1, 1, n, dfn[x], dfn[bot[x]]);
assert(!tmp.a[1][0] && !tmp.a[1][1]);
return std::min(tmp.a[0][0], tmp.a[0][1]);
}
inline void upd(int x, int k) {
a[x] += k;
while (top[x] != 1) {
h[f[top[x]]] -= qry(top[x]);
qadd(1, 1, n, dfn[x]);
h[f[top[x]]] += qry(top[x]);
x = f[top[x]];
}
qadd(1, 1, n, dfn[x]);
}
inline void work() {
dfs1(1), dfs2(1, 1), dfs3(1), build(1, 1, n);
read(m);
while (m--) {
static char opt[5];
int x, y;
scanf("%s", opt);
if (*opt == 'Q') read(x), printf("%lld
", qry(x));
else read(x), read(y), upd(x, y);
}
}
inline void init() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
int x, y;
for (int i = 1; i < n; ++i) read(x), read(y), adde(x, y);
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}