题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=5210
题解
令 (dp[x][0]) 表示以 (x) 为根的子树中的包含 (x) 的连通块的点权和最大值，(dp[x][1]) 为 (x) 的所有孩子中的子树的连通块点权和最大值。
于是有这样的式子：
[dp[x][0] = max(w_x+sum_{yin child_x} dp[y][0], 0)\dp[x][1] = max_{yin child_x} max(dp[y][0], dp[y][1])
]
（其实似乎把 (dp[x][1]) 算上 (dp[x][0]) 的内容也没什么问题，但是我一开始就这样想的不想改了）
现在把这个 (dp) 动态化。令树剖以后，(x) 的重儿子为 (son_x)，(x) 的轻儿子的集合为 (light_x)。令 (h[x][0] = sumlimits_{y in light_x} dp[y][0])，(h[x][1] = maxlimits_{yin light_x} max(dp[y][0], dp[y][1]))。
于是上面的方程可以改写为
[dp[x][0] = max(w_x+h[x][0] + dp[son_x][0], 0)\dp[x][1] = max(h[x][1], dp[son_x][1], dp[son_x][0])
]
于是矩阵（矩乘是把乘法看成加法，加法看成取 (max)）就长这样：
[egin{bmatrix}h[x][0] + w_x & -infty & 0\ 0 & 0 & h[x][1] \ -infty & -infty & 0end{bmatrix} imes egin{bmatrix} dp[son_x][0] \ dp[son_x][1] \ 0 end{bmatrix} = egin{bmatrix} dp[x][0] \ dp[x][1] \ 0 end{bmatrix}
]
然后就套一个动态 DP 的板子就可以了。
有一个需要注意的地方就是因为 (dp[x][1]) 是取 (max) 的，所以在更新 (dp[x][1]) 的时候需要用一个可删除堆来维护最大值。
昨天这道题因为一个 ll 没有写调了几个小时。
单次询问是 (O(log n)) 的，单次修改是 (O(log^2 n))。
#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][2], h[N][2], hh[N][2];
struct Heap {
std::priority_queue<ll> q, p;
inline void sync() { while (!q.empty() && !p.empty() && q.top() == p.top()) q.pop(), p.pop(); }
inline void push(ll x) { q.push(x); sync(); }
inline void del(ll x) { p.push(x), sync(); }
inline ll top() { sync(); return q.top(); }
inline bool empty() { sync(); return q.empty(); }
inline int size() { sync(); return q.size() - p.size·(); }
} q[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[3][3];
inline Matrix() { memset(a, 0, sizeof(a)); }
inline Matrix operator * (const Matrix &b) {
Matrix c;
c.a[0][0] = std::max(std::max(a[0][0] + b.a[0][0], a[0][1] + b.a[1][0]), a[0][2] + b.a[2][0]);
c.a[0][1] = std::max(std::max(a[0][0] + b.a[0][1], a[0][1] + b.a[1][1]), a[0][2] + b.a[2][1]);
c.a[0][2] = std::max(std::max(a[0][0] + b.a[0][2], a[0][1] + b.a[1][2]), a[0][2] + b.a[2][2]);
c.a[1][0] = std::max(std::max(a[1][0] + b.a[0][0], a[1][1] + b.a[1][0]), a[1][2] + b.a[2][0]);
c.a[1][1] = std::max(std::max(a[1][0] + b.a[0][1], a[1][1] + b.a[1][1]), a[1][2] + b.a[2][1]);
c.a[1][2] = std::max(std::max(a[1][0] + b.a[0][2], a[1][1] + b.a[1][2]), a[1][2] + b.a[2][2]);
c.a[2][0] = std::max(std::max(a[2][0] + b.a[0][0], a[2][1] + b.a[1][0]), a[2][2] + b.a[2][0]);
c.a[2][1] = std::max(std::max(a[2][0] + b.a[0][1], a[2][1] + b.a[1][1]), a[2][2] + b.a[2][1]);
c.a[2][2] = std::max(std::max(a[2][0] + b.a[0][2], a[2][1] + b.a[1][2]), a[2][2] + b.a[2][2]);
return c;
}
} 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) {
dp[x][0] = a[x];
for fec(i, x, y) if (y != fa) {
dfs3(y, x);
dp[x][0] += dp[y][0];
smax(dp[x][1], std::max(dp[y][1], dp[y][0]));
if (y != son[x]) h[x][0] += dp[y][0], smax(h[x][1], std::max(dp[y][1], dp[y][0])), q[x].push(std::max(dp[y][1], dp[y][0]));
}
smax(dp[x][0], 0);
}
inline void build(int o, int L, int R) {
if (L == R) {
int x = pre[L];
t[o].a[0][0] = h[x][0] + a[x], t[o].a[0][1] = -INF, t[o].a[0][2] = 0;
t[o].a[1][0] = 0, t[o].a[1][1] = 0, t[o].a[1][2] = h[x][1];
t[o].a[2][0] = -INF, t[o].a[2][1] = -INF, t[o].a[2][2] = 0;
return;
}
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) {
int x = pre[L];
t[o].a[0][0] = h[x][0] + a[x], t[o].a[0][1] = -INF, t[o].a[0][2] = 0;
t[o].a[1][0] = 0, t[o].a[1][1] = 0, t[o].a[1][2] = h[x][1];
t[o].a[2][0] = -INF, t[o].a[2][1] = -INF, t[o].a[2][2] = 0;
return;
}
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 Matrix qry(int x) { return qsum(1, 1, n, dfn[x], dfn[bot[x]]) * Matrix(); }
inline void upd(int x, int k) {
a[x] = k;
while (top[x] != 1) {
Matrix tmp1 = qry(top[x]);
qadd(1, 1, n, dfn[x]);
Matrix tmp2 = qry(top[x]);
int fa = f[top[x]];
h[fa][0] += tmp2.a[0][0] - tmp1.a[0][0];
q[fa].del(std::max(tmp1.a[0][0], tmp1.a[1][0])), q[fa].push(std::max(tmp2.a[0][0], tmp2.a[1][0])), h[fa][1] = q[fa].top();
x = fa;
}
qadd(1, 1, n, dfn[x]);
}
inline void work() {
dfs1(1), dfs2(1, 1), dfs3(1), build(1, 1, n);
Matrix tmp;
while (m--) {
static char opt[5];
int x, y;
scanf("%s", opt);
if (*opt == 'Q') read(x), tmp = qry(x), printf("%lld
", std::max(tmp.a[0][0], tmp.a[1][0]));
else read(x), read(y), upd(x, y);
}
}
inline void init() {
read(n), read(m);
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;
}