洛谷 P2590 [ZJOI2008] 树的统计

// ★ 正解：树链剖分 ＋ 一棵**同时维护「和」与「最大值」**的线段树
//
// ============ 这道题和本章原题（P3384）差在哪儿 ============
//
//   剖分那一半 —— 两趟遍历、跳链、`top`/`dfn`/`siz` —— **一个字都不用改**。
//   换掉的只有线段树里放什么：
//
//       P3384：一个 `sum`，支持「区间加」                 幺元 0
//       这道题：一个 `sum` ＋ 一个 `mx`，支持「单点赋值」   幺元 0 和 **−∞**
//
// ⚠⚠ 而这个「换」里唯一会咬人的就是那个 **−∞**：
//   题面写着「权值 `w` 在 **−3×10⁴ 到 3×10⁴** 之间」—— **可以是负的**。
//   `mx` 的初值（以及跳链时那个累加器的初值）写成 0，负权路径上就会答出一个 0 来。
//   ⇒ 这是本页第一个错法，也是这一页的主线。
//
// ★ 另外两条不在剖分里的：
//   ① `CHANGE u t` 是**赋值**不是加；
//   ② 输入顺序是「先 n−1 条边，再 n 个权值」—— 和 P3384 **正好相反**。
//
// ★ 要不要 `long long`：路径最多 `n = 3×10⁴` 个点，`|w| ≤ 3×10⁴`
//   ⇒ `|和| ≤ 9×10⁸ < 2³¹−1 = 2.147×10⁹`，**`int` 就够，余量 2.39 倍**。
//   这里仍写 `long long`（代价是零），而 `p2590Int.cpp` 是那份 `int` 的 ——
//   它**一次都不会错**，见解析页第 ⑥ 步。
#include <bits/stdc++.h>
using namespace std;

static const int NEG = INT_MIN / 2;
static int n, q;
static vector<int> g[30005];
static int w[30005];
static int fa[30005], dep[30005], siz[30005], son[30005];
static int top_[30005], dfn[30005], rnk[30005], bfsOrder[30005], cnt;

/* ---------- 线段树：单点赋值 + 区间求和 / 区间最大值（没有懒标记） ---------- */
static long long sum_[120005];
static int mx_[120005];
static void pull(int p) {
    sum_[p] = sum_[p << 1] + sum_[p << 1 | 1];
    mx_[p] = max(mx_[p << 1], mx_[p << 1 | 1]);
}
static void build(int p, int l, int r) {
    if (l == r) { sum_[p] = w[rnk[l]]; mx_[p] = w[rnk[l]]; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pull(p);
}
static void setAt(int p, int l, int r, int pos, int v) {
    if (l == r) { sum_[p] = v; mx_[p] = v; return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) setAt(p << 1, l, mid, pos, v); else setAt(p << 1 | 1, mid + 1, r, pos, v);
    pull(p);
}
static long long qSum(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum_[p];
    int mid = (l + r) >> 1;
    long long s = 0;
    if (L <= mid) s += qSum(p << 1, l, mid, L, R);
    if (R > mid) s += qSum(p << 1 | 1, mid + 1, r, L, R);
    return s;
}
static int qMax(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return mx_[p];
    int mid = (l + r) >> 1;
    int s = NEG;
    if (L <= mid) s = max(s, qMax(p << 1, l, mid, L, R));
    if (R > mid) s = max(s, qMax(p << 1 | 1, mid + 1, r, L, R));
    return s;
}

/* ---------- 两趟遍历（都不递归；顶格 n = 3×10⁴ 的链递归也危险，习惯别改） ---------- */
static void pass1() {
    int head = 0, tail = 0;
    bfsOrder[tail++] = 1; fa[1] = 0; dep[1] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    for (int i = 1; i <= n; i++) { siz[i] = 1; son[i] = 0; }
    for (int i = n - 1; i >= 0; i--) {
        int u = bfsOrder[i], p = fa[u];
        if (!p) continue;
        siz[p] += siz[u];
        if (!son[p] || siz[u] > siz[son[p]]) son[p] = u;
    }
}
static void pass2() {
    static int st[30005];
    int sp = 0; cnt = 0;
    top_[1] = 1; st[sp++] = 1;
    while (sp) {
        int u = st[--sp];
        dfn[u] = ++cnt; rnk[cnt] = u;
        for (int v : g[u]) if (v != fa[u] && v != son[u]) { top_[v] = v; st[sp++] = v; }
        if (son[u]) { top_[son[u]] = top_[u]; st[sp++] = son[u]; }
    }
}

/* ---------- 路径：和「区间加」那道题一模一样的跳法 ---------- */
static long long pathSum(int x, int y) {
    long long s = 0;
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        s += qSum(1, 1, n, dfn[top_[x]], dfn[x]);
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return s + qSum(1, 1, n, dfn[x], dfn[y]);            // ★ 端点也算：没有 +1
}
static int pathMax(int x, int y) {
    int s = NEG;                                          // ★★ 幺元是 −∞，不是 0
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        s = max(s, qMax(1, 1, n, dfn[top_[x]], dfn[x]));
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return max(s, qMax(1, 1, n, dfn[x], dfn[y]));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n)) return 0;
    for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }
    for (int i = 1; i <= n; i++) cin >> w[i];             // ⚠ 权值在边之后，和 P3384 相反
    pass1(); pass2();
    build(1, 1, n);

    cin >> q;
    string op;
    for (int i = 0; i < q; i++) {
        int a, b; cin >> op >> a >> b;
        if (op == "CHANGE") setAt(1, 1, n, dfn[a], b);    // ★ 赋值，不是加
        else if (op == "QMAX") cout << pathMax(a, b) << '\n';
        else cout << pathSum(a, b) << '\n';
    }
    return 0;
}

// P2590 的「触发条件计数器」：读一组数据，打一行 CSV
//
//   negmax   = 1 ⟺ 存在一次 QMAX，它那条路径上的最大值 **< 0**（①MaxZero 的触发条件）
//   chgnz    = 1 ⟺ 存在一次 `CHANGE u t` 且**当时** `w[u] ≠ 0`（②ChangeAdd 的第一层）
//   chgseen  = 1 ⟺ 上面那种 CHANGE 之后，还有一次询问真的碰到了那个 u（第二层）
//   lcadiff  = 1 ⟺ 存在一次询问，「漏掉浅的那个端点」会让答案变（③SkipLca 的触发条件）
//   maxabs   = 所有 QSUM 答案绝对值的最大值（④Int 的那条线：≥ 2³¹ 才可能烂）
//
// ★ 全部拿**暴力那条路**算，和被测的剖分代码一行都不共享。
#include <bits/stdc++.h>
using namespace std;
static int n, q;
static vector<int> g[30005];
static int w[30005], fa[30005], dep[30005], bfsOrder[30005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n)) return 0;
    for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }
    for (int i = 1; i <= n; i++) cin >> w[i];
    int head = 0, tail = 0;
    bfsOrder[tail++] = 1; fa[1] = 0; dep[1] = 1;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (int v : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; bfsOrder[tail++] = v; }
    }
    cin >> q;
    int negmax = 0, chgnz = 0, chgseen = 0, lcadiff = 0;
    long long maxabs = 0;
    vector<int> dirty(n + 1, 0);
    string op;
    for (int i = 0; i < q; i++) {
        int a, b; cin >> op >> a >> b;
        if (op == "CHANGE") { if (w[a] != 0) { chgnz = 1; dirty[a] = 1; } w[a] = b; continue; }
        /* 走一遍路径，顺手把「路径上有哪些点」「谁是 LCA」都收下来 */
        vector<int> pts;
        int x = a, y = b;
        while (dep[x] > dep[y]) { pts.push_back(x); x = fa[x]; }
        while (dep[y] > dep[x]) { pts.push_back(y); y = fa[y]; }
        while (x != y) { pts.push_back(x); pts.push_back(y); x = fa[x]; y = fa[y]; }
        int lca = x;
        long long s = 0; int mx = INT_MIN / 2;
        for (int p : pts) { s += w[p]; mx = max(mx, w[p]); }
        long long sNo = s; int mxNo = mx;                       // 不含 LCA 的那一版
        s += w[lca]; mx = max(mx, w[lca]);
        for (int p : pts) if (dirty[p]) chgseen = 1;
        if (dirty[lca]) chgseen = 1;
        if (op == "QMAX") { if (mx < 0) negmax = 1; if (mx != (pts.empty() ? INT_MIN / 2 : mxNo)) lcadiff = 1; }
        else { maxabs = max(maxabs, s < 0 ? -s : s); if (s != sNo) lcadiff = 1; }
    }
    printf("negmax,%d\nchgnz,%d\nchgseen,%d\nlcadiff,%d\nmaxabs,%lld\n", negmax, chgnz, chgseen, lcadiff, maxabs);
    return 0;
}