洛谷 P4315 月下“毛景树”

// ★ 正解：树链剖分（**边权版**）＋ 一棵带**两个懒标记**的线段树
//
// ============ 这道题比前两道多的东西，只有两件 ============
//
// ① **边权**。本章第 12 步那一句：**一条边的权，存到它「深的那一端」那个点上**。
//    于是「路径上的边」变成「路径上的点」，⚠ 但要**去掉 LCA 那一格**
//    （LCA 头顶那条边不在这条路径上）⇒ 收尾那一段是 `[dfn[x] + 1, dfn[y]]`。
//    ★ 而 `Change k w` 给的是**边号**，所以还要记一张 `k → 那条边深的那一端` 的表。
//
// ② ★★★ **两个懒标记**：`Cover`（区间赋值）和 `Add`（区间加）。
//    它们**不是对称的**，谁压谁有明确的顺序：
//
//        来一个 Cover ⇒ 这一段被彻底重写 ⇒ **之前攒的 add 全部作废**（`add = 0`）
//        来一个 Add   ⇒ 如果这一段已经有 cover，就把 add 并进 cover 里（`cov += v`）；
//                       否则老老实实攒进 add
//        下推时       ⇒ **先放 cover，再放 add**（顺序反了就等于把作废的账又翻出来）
//
//    ⇒ 一句话记：**Cover 是「重写」，Add 是「修补」；重写会把之前的修补一笔勾销。**
//    ⚠ 漏掉那句 `add = 0` 就是本页第一个错法，而它**官方样例照过不误**。
//
// ★ 要不要 long long：题面保证「任意时刻毛毛果个数不超过 10⁹」< 2³¹ ⇒ `int` 就够。
//   这里仍写 `long long`（代价是零）。
#include <bits/stdc++.h>
using namespace std;

static int n;
static vector<pair<int, int>> g[100005];        // (邻居, 边号)
static int fa[100005], dep[100005], siz[100005], son[100005], upEdge[100005];
static int top_[100005], dfn[100005], rnk[100005], bfsOrder[100005], cnt;
static int epoint[100005];                      // 第 k 条边 → 它「深的那一端」那个点
static long long w[100005];                     // 点上挂的边权（根那一格恒为 0，永远不会被碰到）

/* ---------- 线段树：区间赋值 + 区间加 + 区间最大值 ---------- */
static long long mx_[400005], add_[400005], cov_[400005];
static bool hasCov[400005];
static void pull(int p) { mx_[p] = max(mx_[p << 1], mx_[p << 1 | 1]); }
static void applyCov(int p, long long v) {
    mx_[p] = v; cov_[p] = v; hasCov[p] = true;
    add_[p] = 0;                                 // ★★★ 这一行就是这道题的全部难点：重写 ⇒ 修补作废
}
static void applyAdd(int p, long long v) {
    mx_[p] += v;
    if (hasCov[p]) cov_[p] += v; else add_[p] += v;
}
static void push(int p) {
    if (hasCov[p]) { applyCov(p << 1, cov_[p]); applyCov(p << 1 | 1, cov_[p]); hasCov[p] = false; }
    if (add_[p]) { applyAdd(p << 1, add_[p]); applyAdd(p << 1 | 1, add_[p]); add_[p] = 0; }
}
static void build(int p, int l, int r) {
    add_[p] = 0; hasCov[p] = false; cov_[p] = 0;
    if (l == r) { 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 rangeCov(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) { applyCov(p, v); return; }
    push(p);
    int mid = (l + r) >> 1;
    if (L <= mid) rangeCov(p << 1, l, mid, L, R, v);
    if (R > mid) rangeCov(p << 1 | 1, mid + 1, r, L, R, v);
    pull(p);
}
static void rangeAdd(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) { applyAdd(p, v); return; }
    push(p);
    int mid = (l + r) >> 1;
    if (L <= mid) rangeAdd(p << 1, l, mid, L, R, v);
    if (R > mid) rangeAdd(p << 1 | 1, mid + 1, r, L, R, v);
    pull(p);
}
static long long rangeMax(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return mx_[p];
    push(p);
    int mid = (l + r) >> 1;
    long long s = LLONG_MIN;
    if (L <= mid) s = max(s, rangeMax(p << 1, l, mid, L, R));
    if (R > mid) s = max(s, rangeMax(p << 1 | 1, mid + 1, r, L, R));
    return s;
}

/* ---------- 两趟遍历（都不递归：顶格就是一条 10⁵ 个点的链） ---------- */
static void pass1() {
    int head = 0, tail = 0;
    bfsOrder[tail++] = 1; fa[1] = 0; dep[1] = 1; upEdge[1] = 0;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (auto [v, id] : g[u]) if (v != fa[u]) {
            fa[v] = u; dep[v] = dep[u] + 1; upEdge[v] = id; epoint[id] = v; 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[100005];
    int sp = 0; cnt = 0;
    top_[1] = 1; st[sp++] = 1;
    while (sp) {
        int u = st[--sp];
        dfn[u] = ++cnt; rnk[cnt] = u;
        for (auto [v, id] : g[u]) { (void)id; 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]; }
    }
}

/* ---------- 路径：跳链，收尾那一段左端 +1（★ 跳过 LCA 那一格） ---------- */
enum Kind { COVER, ADD, MAXQ };
static long long onPath(int x, int y, long long v, Kind kind) {
    long long res = LLONG_MIN;
    auto seg = [&](int L, int R) {
        if (L > R) return;
        if (kind == COVER) rangeCov(1, 1, n, L, R, v);
        else if (kind == ADD) rangeAdd(1, 1, n, L, R, v);
        else res = max(res, rangeMax(1, 1, n, L, R));
    };
    while (top_[x] != top_[y]) {
        if (dep[top_[x]] < dep[top_[y]]) swap(x, y);
        seg(dfn[top_[x]], dfn[x]);
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    seg(dfn[x] + 1, dfn[y]);                     // ★★ +1：LCA 头顶那条边不在这条路径上
    return res == LLONG_MIN ? 0 : res;           // ⚠ u = v ⇒ 一条边都没有，本页一律打 0
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n)) return 0;
    static long long ew[100005];
    for (int i = 1; i < n; i++) {
        int u, v; long long c; cin >> u >> v >> c;
        g[u].push_back({v, i}); g[v].push_back({u, i}); ew[i] = c;
    }
    pass1(); pass2();
    for (int i = 1; i <= n; i++) w[i] = 0;
    for (int i = 1; i < n; i++) w[epoint[i]] = ew[i];    // ★ 边权下放到深的那一端
    build(1, 1, n);

    string op;
    while (cin >> op && op != "Stop") {
        if (op == "Change") {
            int k; long long v; cin >> k >> v;
            rangeCov(1, 1, n, dfn[epoint[k]], dfn[epoint[k]], v);
        } else {
            int x, y; cin >> x >> y;
            if (op == "Max") cout << onPath(x, y, 0, MAXQ) << '\n';
            else { long long v; cin >> v; onPath(x, y, v, op == "Cover" ? COVER : ADD); }
        }
    }
    return 0;
}

// P4315 的「触发条件计数器」：读一组数据，打一行 CSV
//
//   covafteradd = 1 ⟺ 存在一次 `Cover`，而它**前面**出现过 `Add`
//                     （①NoClear / ②PushOrder 的第一层：两个标记得真的压到一起）
//   flipped     = 1 ⟺ 存在一条输入边，它的**第二个端点是父亲**（④EdgeSide 的触发条件）
//   changemis   = 1 ⟺ 存在一次 `Change k`，而 `k` 和「第 k 条边深的那一端」不是同一个编号
//                     （⑤ChangeIdx 的触发条件）
//   lcadiff     = 1 ⟺ 存在一次 `Max`，把「LCA 头顶那条边」也算进去会让答案变
//                     （③NoSkip 的触发条件；⚠ 只是**第一层** —— 那一版连 Cover/Add 也写歪了）
//
// ★ 全部拿**暴力那条路**算，和被测的剖分代码一行都不共享。
#include <bits/stdc++.h>
using namespace std;
static int n;
static vector<pair<int, int>> g[100005];
static int fa[100005], dep[100005], upEdge[100005], bfsOrder[100005];
static long long val[100005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n)) return 0;
    vector<int> ea(n + 1, 0), eb(n + 1, 0);
    for (int i = 1; i < n; i++) {
        int u, v; long long w; cin >> u >> v >> w;
        g[u].push_back({v, i}); g[v].push_back({u, i}); val[i] = w; ea[i] = u; eb[i] = v;
    }
    int head = 0, tail = 0;
    bfsOrder[tail++] = 1; fa[1] = 0; dep[1] = 1; upEdge[1] = 0;
    while (head < tail) {
        int u = bfsOrder[head++];
        for (auto [v, id] : g[u]) if (v != fa[u]) { fa[v] = u; dep[v] = dep[u] + 1; upEdge[v] = id; bfsOrder[tail++] = v; }
    }
    vector<int> epoint(n + 1, 0);
    for (int i = 1; i < n; i++) epoint[i] = (fa[eb[i]] == ea[i]) ? eb[i] : ea[i];

    int covafteradd = 0, flipped = 0, changemis = 0, lcadiff = 0, sawAdd = 0;
    for (int i = 1; i < n; i++) if (epoint[i] != eb[i]) flipped = 1;

    string op;
    while (cin >> op && op != "Stop") {
        if (op == "Change") { int k; long long w; cin >> k >> w; if (epoint[k] != k) changemis = 1; val[k] = w; continue; }
        int x, y; cin >> x >> y;
        long long w = 0;
        if (op != "Max") cin >> w;
        if (op == "Add") sawAdd = 1;
        if (op == "Cover" && sawAdd) covafteradd = 1;
        vector<int> es;
        while (dep[x] > dep[y]) { es.push_back(upEdge[x]); x = fa[x]; }
        while (dep[y] > dep[x]) { es.push_back(upEdge[y]); y = fa[y]; }
        while (x != y) { es.push_back(upEdge[x]); es.push_back(upEdge[y]); x = fa[x]; y = fa[y]; }
        int lca = x;
        if (op == "Cover") { for (int e : es) val[e] = w; }
        else if (op == "Add") { for (int e : es) val[e] += w; }
        else {
            long long mx = 0, mx2;
            for (int e : es) mx = max(mx, val[e]);
            mx2 = (lca == 1) ? max(mx, 0LL) : max(mx, val[upEdge[lca]]);   // 把 LCA 头顶那条也算进去
            if (mx != mx2) lcadiff = 1;
        }
    }
    printf("covafteradd,%d\nflipped,%d\nchangemis,%d\nlcadiff,%d\n", covafteradd, flipped, changemis, lcadiff);
    return 0;
}