洛谷 P3178 [HAOI2015] 树上操作

// P3178 [HAOI2015] 树上操作 —— 正解：**DFS 序 ＋ 两个树状数组**
//
// ★★★ 这道题放在第 52 章题单里，是为了让你亲眼看到**树上差分不够用**：
//   差分那一套是**离线**的 —— 先把所有修改叠成标记，最后一趟子树求和还原。
//   而这道题是**边改边问**（p3178Offline.cpp 就是「非要离线」的下场）。
//
// ⚠⚠ 而题单原来那句「正解是树链剖分」**是多余的**：这道题的三种操作用
//   **DFS 序 ＋ 两个树状数组**就能全部做完，`O((N+M) log N)`，而且更短更快。
//   道理在于「查询」的形状特别老实 —— 它问的是**根到 x**，不是任意两点之间。
//
// ★★★ 推一遍就出来了。设 `dep[根] = 1`，问的是 `ans(x) = Σ_{v 是 x 的祖先或自己} val(v)`：
//   ① `1 x a`（单点加）：只有 x 一个点变了 ⇒ 对 ans(y) 的贡献是
//      「y 在 x 的子树里就 +a，否则 0」；
//   ② `2 x a`（子树加）：x 的子树里每个点都 +a ⇒ 对 ans(y) 的贡献是
//      「y 的祖先里有几个落在 x 的子树里」× a。而 y 在 x 子树里时，
//      那些祖先正好是 x…y 这一段 ⇒ 个数 = `dep[y] − dep[x] + 1`；y 不在时是 0。
//
//   ⇒ **两条都能写成 `k·dep[y] + b` 的形状，而且都只作用在「x 的子树」这一段连续的 DFS 序上**：
//        ① k = 0,  b = a
//        ② k = a,  b = a·(1 − dep[x])
//   ⇒ 于是只要两棵「区间加、单点查」的树状数组：一棵管 k，一棵管 b，
//      答案就是 `ans(x) = dep[x] · K(tin[x]) + B(tin[x])`。
//
// ★ 「要不要 long long」是一句乘法：单点最大 |val| ≈ 10⁶ + 10⁵ × 10⁶ ≈ 10¹¹，
//   路径最多 10⁵ 个点 ⇒ 答案能到 **10¹⁶**，而 long long 的上限是 9.2×10¹⁸ ⇒ 够，余量约 920 倍；
//   ⚠ 而 int 差着五个数量级 —— 见 p3178Int.cpp。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], ecnt;
int tin[MAXN], tout[MAXN], dep[MAXN], n, m, timer_;
long long bitK[MAXN], bitB[MAXN];

inline void addEdge(int u, int v) { to_[++ecnt] = v; nxt_[ecnt] = head_[u]; head_[u] = ecnt; }

inline void bitAdd(long long* c, int i, long long v) { for (; i <= n; i += i & (-i)) c[i] += v; }
inline long long bitAsk(long long* c, int i) { long long s = 0; for (; i > 0; i -= i & (-i)) s += c[i]; return s; }
/* 区间 [l, r] 加 v，单点查前缀和 */
inline void rangeAdd(long long* c, int l, int r, long long v) { bitAdd(c, l, v); bitAdd(c, r + 1, -v); }

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    vector<long long> init(n + 1);
    for (int i = 1; i <= n; i++) if (scanf("%lld", &init[i]) != 1) return 0;
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        addEdge(x, y); addEdge(y, x);
    }

    /* 迭代 DFS 求 tin / tout / dep（⚠ 顶格 10⁵ 排成一条链，递归有 10 万层）*/
    {
        vector<int> st(n + 5), it(n + 5);
        int top = 0;
        st[top] = 1; it[1] = head_[1]; dep[1] = 1; tin[1] = ++timer_;
        vector<int> par(n + 1, 0);
        while (top >= 0) {
            int u = st[top];
            int e = it[u];
            if (e == 0) { tout[u] = timer_; top--; continue; }
            it[u] = nxt_[e];
            int v = to_[e];
            if (v == par[u]) continue;
            par[v] = u; dep[v] = dep[u] + 1; tin[v] = ++timer_; it[v] = head_[v];
            st[++top] = v;
        }
    }

    for (int i = 1; i <= n; i++) rangeAdd(bitB, tin[i], tout[i], init[i]);   // 初值 = n 次单点加

    for (int q = 0; q < m; q++) {
        int op, x;
        long long a;
        if (scanf("%d %d", &op, &x) != 2) return 0;
        if (op == 1) {
            if (scanf("%lld", &a) != 1) return 0;
            rangeAdd(bitB, tin[x], tout[x], a);
        } else if (op == 2) {
            if (scanf("%lld", &a) != 1) return 0;
            rangeAdd(bitK, tin[x], tout[x], a);
            rangeAdd(bitB, tin[x], tout[x], a * (1LL - dep[x]));
        } else {
            long long k = bitAsk(bitK, tin[x]), b = bitAsk(bitB, tin[x]);
            printf("%lld\n", k * dep[x] + b);
        }
    }
    return 0;
}

// P3178 的账：这份数据长什么样、几个错法的触发条件成不成立、两条路各做多少次基本动作
//
// 用法：./p3178Count <csv|table> < 一份输入
//
// ★ 数四个决定成败的东西：
//   ① **修改和询问有没有真的交错**（询问后面还有修改）—— 错法④Offline 的触发条件；
//   ② **有没有一次单点加落在某个后续询问点的严格祖先上** —— 错法③AsSub 的触发条件；
//   ③ **中间值的绝对值最大到多少** —— 错法①Int 的那条数值线；
//   ④ **爬到根一共要走多少个点** —— 第二版（p3178Climb）那张顶格表的主角。
// ⚠ ①②是 O(m²) 数的，所以 m > 2000 时直接报 −1（顶格表用不着它们）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
static int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], ecnt;
static int tin[MAXN], tout[MAXN], dep[MAXN], par[MAXN], order_[MAXN], n, m, timer_;
static long long val[MAXN];

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 1; i <= n; i++) if (scanf("%lld", &val[i]) != 1) return 0;
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        to_[++ecnt] = y; nxt_[ecnt] = head_[x]; head_[x] = ecnt;
        to_[++ecnt] = x; nxt_[ecnt] = head_[y]; head_[y] = ecnt;
    }
    {
        vector<int> st(n + 5), it(n + 5);
        int top = 0;
        st[top] = 1; it[1] = head_[1]; dep[1] = 1; tin[1] = ++timer_; order_[timer_] = 1;
        while (top >= 0) {
            int u = st[top], e = it[u];
            if (e == 0) { tout[u] = timer_; top--; continue; }
            it[u] = nxt_[e];
            int v = to_[e];
            if (v == par[u]) continue;
            par[v] = u; dep[v] = dep[u] + 1; tin[v] = ++timer_; order_[timer_] = v; it[v] = head_[v];
            st[++top] = v;
        }
    }
    int maxDep = 0;
    for (int i = 1; i <= n; i++) maxDep = max(maxDep, dep[i]);

    vector<int> op(m), ox(m);
    vector<long long> oa(m, 0);
    for (int i = 0; i < m; i++) {
        if (scanf("%d %d", &op[i], &ox[i]) != 2) return 0;
        if (op[i] != 3 && scanf("%lld", &oa[i]) != 1) return 0;
    }

    /* ★ 一遍模拟，同时量「答案」和「中间值最大绝对值」（这一份自己用 long long） */
    long long maxAbs = 0, climbSteps = 0, qCnt = 0, ansNonZero = 0;
    vector<long long> lazySub(n + 1, 0);
    for (int i = 1; i <= n; i++) maxAbs = max(maxAbs, llabs(val[i]));
    for (int i = 0; i < m; i++) {
        if (op[i] == 1) { val[ox[i]] += oa[i]; maxAbs = max(maxAbs, llabs(val[ox[i]])); }
        else if (op[i] == 2) {
            for (int j = tin[ox[i]]; j <= tout[ox[i]]; j++) {
                val[order_[j]] += oa[i];
                maxAbs = max(maxAbs, llabs(val[order_[j]]));
            }
        } else {
            long long s = 0;
            for (int u = ox[i]; u; u = par[u]) { s += val[u]; climbSteps++; }
            maxAbs = max(maxAbs, llabs(s));
            qCnt++;
            if (s != 0) ansNonZero++;
        }
    }
    (void)lazySub;

    long long interleave = -1, asSub = -1, noDep = -1;
    if (m <= 2000) {
        interleave = 0; asSub = 0; noDep = 0;
        for (int i = 0; i < m; i++) {
            if (op[i] != 3) continue;
            for (int j = i + 1; j < m; j++) if (op[j] != 3) { interleave++; break; }
        }
        for (int i = 0; i < m; i++) {
            if (op[i] != 1 || oa[i] == 0) continue;
            for (int j = i + 1; j < m; j++)
                if (op[j] == 3 && tin[ox[i]] <= tin[ox[j]] && tin[ox[j]] <= tout[ox[i]] && dep[ox[j]] > dep[ox[i]]) { asSub++; break; }
        }
        for (int i = 0; i < m; i++) {
            if (op[i] != 2 || oa[i] == 0) continue;
            for (int j = i + 1; j < m; j++)
                if (op[j] == 3 && tin[ox[i]] <= tin[ox[j]] && tin[ox[j]] <= tout[ox[i]]) { noDep++; break; }
        }
    }

    vector<pair<string, string> > out;
    out.push_back(make_pair("n", to_string(n)));
    out.push_back(make_pair("m", to_string(m)));
    out.push_back(make_pair("maxdep", to_string(maxDep)));
    out.push_back(make_pair("queries", to_string(qCnt)));
    out.push_back(make_pair("ans_nonzero", to_string(ansNonZero)));
    out.push_back(make_pair("max_abs", to_string(maxAbs)));
    out.push_back(make_pair("over_int", to_string(maxAbs > 2147483647LL ? 1 : 0)));
    out.push_back(make_pair("interleave", to_string(interleave)));
    out.push_back(make_pair("trig_assub", to_string(asSub)));
    out.push_back(make_pair("trig_nodep", to_string(noDep)));
    out.push_back(make_pair("climb_steps", to_string(climbSteps)));
    if (mode == "csv") for (size_t i = 0; i < out.size(); i++) printf("%s,%s\n", out[i].first.c_str(), out[i].second.c_str());
    else for (size_t i = 0; i < out.size(); i++) printf("  %-14s %s\n", out[i].first.c_str(), out[i].second.c_str());
    return 0;
}