[HAOI2015] 树上操作

解法一: dfs序

核心思路

修改点u的值,会对u的子树上的所有点产生贡献
修改点u为根的子树上的所有点,也会对u的子树上的所有点产生贡献
暴力: 暴力的修改 u子树上的所有点
优化暴力: 加的值都一样: 区间修改,单点查询

解决这道题（Luogu P3178）的核心思路是: “贡献法” + “转化思想”。

我们需要扭转视角：不要去想“我要去遍历这条链求和”，而是去想**“之前的修改操作，对我要查询的这条链产生了多少贡献？”**

1. 核心推导（数学魔法）

设 $dep[x]$ 为节点 $x$ 的深度（根为 1）。我们要查询 $x$ 到根的路径和。

分析操作 1：单点修改 (节点 $u$ 加 $v$ )

物理意义：节点 $u$ 的权值增加了 $v$ 。
谁会受到影响？：只有当 $u$ 在 $x$ 到根的路径上时，查询 $x$ 的结果才会增加。
转化：换句话说，如果 $x$ 在 $u$ 的子树里，那么 $u$ 的增加就会贡献给 $x$ 的路径和。
结论：单点修改 $u$ $\Rightarrow$ $u$ 的子树区间 $[in[u], out[u]]$ 的答案全部 $+v$ 。

分析操作 2：子树修改 (以 $u$ 为根的子树全部加 $v$ )

这是最难的一步。

假设 $x$ 在 $u$ 的子树里（否则不受影响）。
操作是把 $u$ 子树里每个点都加了 $v$ 。
路径上有多少个点被加了？：从 $u$ 到 $x$ 的路径上，所有点都被加了 $v$ 。
点的数量： $dep[x] - dep[u] + 1$ 。
总贡献： $v \times (dep[x] - dep[u] + 1)$ 。
拆开公式：
$\text{贡献} = v \times dep[x] + v \times (1 - dep[u])$
结论：这个贡献由两部分组成：
1. 跟 $dep[x]$ 相关的项：系数是 $v$ 。
2. 常数项（相对于 $x$ 而言）： $v \times (1 - dep[u])$ 。

2. 解决方案：两个树状数组 (BIT)

根据上面的推导，我们需要维护两个支持 区间修改、单点查询 的树状数组（或者线段树）。

我们把问题转化为了在 DFS 序区间 $[in[u], out[u]]$ 上的操作：

$BIT_1$ (维护常数项)
$BIT_2$ (维护 $dep[x]$ 的系数)

对于查询操作 $Ask(x)$ ，最终答案是：

Ans = BIT_1.\text{query}(in[x]) + BIT_2.\text{query}(in[x]) \times dep[x]

操作对应表

原操作	转化后的操作 (在 DFS 序区间 `[in[u], out[u]]` 上)
Op 1: 点 $u$ 加 $v$	$BIT_1$ 区间加 $v$ ( $u$ 只是一个点，但它作为祖先，贡献给了它整个子树)
Op 2: 子树 $u$ 加 $v$	部分 A: $BIT_2$ 区间加 $v$ (对应公式里的 $v \times dep[x]$ ) 部分 B: $BIT_1$ 区间加 $v \times (1 - dep[u])$
Op 3: 查 $x$ 到根之和	$BIT_1.query(in[x]) + BIT_2.query(in[x]) \times dep[x]$

3. 代码实现 (C++)

这里使用 差分树状数组 来实现“区间修改，单点查询”。 (注：普通的 BIT 支持单点修、前缀查。要支持区间修、单点查，需要用差分思想，即 update(l, v), update(r+1, -v))

cpp

#include <iostream>
#include <vector>
using namespace std;

const int N = 100005;
typedef long long ll;

int n, m;
ll w[N]; // 初始权值
vector<int> adj[N];
int in[N], out[N], timer;
int dep[N];

// 树状数组结构体：支持区间修改，单点查询
struct Fenwick {
    ll c[N];
    // 内部实现：单点修改
    void add_point(int x, ll v) {
        for (; x <= n; x += x & -x) c[x] += v;
    }
    // 内部实现：前缀求和
    ll ask_prefix(int x) {
        ll res = 0;
        for (; x; x -= x & -x) res += c[x];
        return res;
    }
    
    // 【外部接口】区间修改 [l, r] 加 v
    void range_add(int l, int r, ll v) {
        add_point(l, v);
        add_point(r + 1, -v);
    }
    // 【外部接口】单点查询 x 的值
    ll query_point(int x) {
        return ask_prefix(x);
    }
} bit1, bit2;

void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    in[u] = ++timer;
    for (int v : adj[u]) {
        if (v != fa) dfs(v, u);
    }
    out[u] = timer;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 1. 建树，生成 DFS 序
    dfs(1, 0);

    // 2. 初始化：把初始权值当做一次 Operation 1
    // 每个点 i 初始有权值 w[i]，相当于对节点 i 进行了一次单点加 w[i]
    for (int i = 1; i <= n; i++) {
        bit1.range_add(in[i], out[i], w[i]);
    }

    // 3. 处理操作
    while (m--) {
        int op, x;
        ll a;
        scanf("%d", &op);
        if (op == 1) { // 单点 x 加 a
            scanf("%d%lld", &x, &a);
            bit1.range_add(in[x], out[x], a);
        }
        else if (op == 2) { // 子树 x 加 a
            scanf("%d%lld", &x, &a);
            // 拆分为两部分贡献
            bit1.range_add(in[x], out[x], a * (1 - dep[x]));
            bit2.range_add(in[x], out[x], a);
        }
        else if (op == 3) { // 查询 x 到根的路径和
            scanf("%d", &x);
            ll ans = bit1.query_point(in[x]) + bit2.query_point(in[x]) * dep[x];
            printf("%lld\n", ans);
        }
    }
    return 0;
}

总结

你看到了吗？虽然 DFS 序无法直接把“链”变成区间，但它利用 “贡献法”，把**“在这个链上的修改”转化为了“对子树区间的影响”**。

这就是那篇笔记里第 3 点 “树链修改，子树查询” 的逆向运用（对偶问题）。一旦你理解了这种贡献拆分（常数项 + 深度系数项），DFS 序的威力就比树链剖分还要简洁！

树链剖分

TODO: 读这个的代码

这是一个非常好的问题！很多人在刚学**树链剖分（HLD）**时都会有这个困惑：

“树剖是为了切分链的，那子树怎么办？是不是要维护两套系统？”

答案是：不需要。树剖天然兼容子树操作。

核心原理：树剖的 DFS 序

树链剖分的核心是两次 DFS。

第一次 DFS：找重儿子（子树最大的儿子）。
第二次 DFS：生成 DFS 序。关键在于，优先遍历重儿子。

因为树剖本质上还是 DFS，所以它保留了 DFS 序最完美的性质： 一颗子树，在 DFS 序中依然是一个连续的区间。

所以，在树剖中：

一条重链 $\Rightarrow$ 是一段连续的区间（这是树剖特意构造的）。
一棵子树 $\Rightarrow$ 也是一段连续的区间（这是 DFS 的天然性质）。

P3178 的树剖解法映射

我们要维护一个线段树，这个线段树是建立在树剖生成的 DFS 序（dfn 数组）之上的。

变量定义

dfn[x]: 节点 $x$ 的新编号（时间戳）。
siz[x]: $x$ 的子树大小。
top[x]: $x$ 所在链的链顶节点。

三个操作的转化

操作 1：单点修改 (节点 $x$ 加 $v$ )

转化：线段树上 [dfn[x], dfn[x]] 区间修改（或单点修改）。

操作 2：子树修改 (子树 $x$ 加 $v$ )

转化：因为子树是连续的，直接在线段树上修改区间 [dfn[x], dfn[x] + siz[x] - 1]。
这就是你疑惑的地方：直接用区间修改即可，不需要任何特殊处理。

操作 3：树链查询 ( $x$ 到根的和)

转化：这是树剖的看家本领。
使用 while (top[x] != top[root]) 循环跳链。
每次查询当前链顶到 $x$ 的区间：query(dfn[top[x]], dfn[x])。
最后当 $x$ 和 $root$ 在同一条重链上时，再查一次：query(dfn[root], dfn[x])。

代码实现 (C++ 树剖模板)

这道题用树剖写，就是一个支持区间修改（Lazy Tag）的线段树 + 树剖跳链逻辑。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 100005;

// === 1. 图与树的结构 ===
int n, m;
ll w[N]; // 初始权值
vector<int> adj[N];

// 树剖核心数组
int fa[N], dep[N], siz[N], son[N]; // DFS1 用
int top[N], dfn[N], rnk[N], cnt;   // DFS2 用

// === 2. 线段树 (支持区间加，区间求和) ===
struct SegTree {
    ll sum[N * 4];
    ll lazy[N * 4];

    void pushup(int p) {
        sum[p] = sum[p * 2] + sum[p * 2 + 1];
    }

    void pushdown(int p, int l, int r) {
        if (lazy[p]) {
            int mid = (l + r) >> 1;
            sum[p * 2] += lazy[p] * (mid - l + 1);
            lazy[p * 2] += lazy[p];
            sum[p * 2 + 1] += lazy[p] * (r - mid);
            lazy[p * 2 + 1] += lazy[p];
            lazy[p] = 0;
        }
    }

    void build(int p, int l, int r) {
        lazy[p] = 0;
        if (l == r) {
            // rnk[l] 是 DFS序为 l 的那个原节点编号
            sum[p] = w[rnk[l]]; 
            return;
        }
        int mid = (l + r) >> 1;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
        pushup(p);
    }

    void update(int p, int l, int r, int ql, int qr, ll v) {
        if (ql <= l && r <= qr) {
            sum[p] += v * (r - l + 1);
            lazy[p] += v;
            return;
        }
        pushdown(p, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid) update(p * 2, l, mid, ql, qr, v);
        if (qr > mid) update(p * 2 + 1, mid + 1, r, ql, qr, v);
        pushup(p);
    }

    ll query(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return sum[p];
        pushdown(p, l, r);
        int mid = (l + r) >> 1;
        ll res = 0;
        if (ql <= mid) res += query(p * 2, l, mid, ql, qr);
        if (qr > mid) res += query(p * 2 + 1, mid + 1, r, ql, qr);
        return res;
    }
} tr;

// === 3. 树剖的两个 DFS ===

// 第一遍：计算大小、深度、父节点、重儿子
void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    son[u] = 0;
    int max_siz = -1;

    for (int v : adj[u]) {
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > max_siz) {
            max_siz = siz[v];
            son[u] = v; // 记录重儿子
        }
    }
}

// 第二遍：连接重链，生成 DFS 序
// topf: 当前链的链顶节点
void dfs2(int u, int topf) {
    top[u] = topf;
    dfn[u] = ++cnt;
    rnk[cnt] = u; // 记录反向映射，建树用

    if (!son[u]) return; // 叶子节点

    // 【关键】优先遍历重儿子，保证重链在 DFS 序上连续
    dfs2(son[u], topf);

    for (int v : adj[u]) {
        if (v == fa[u] || v == son[u]) continue;
        // 轻儿子，新的链顶是它自己
        dfs2(v, v);
    }
}

// === 4. 树剖逻辑封装 ===

// 路径查询 x 到 y 的和 (本题 y 固定为 1)
ll query_path(int x, int y) {
    ll res = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        // 查询当前链顶 top[x] 到 x 的这一段
        res += tr.query(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    // 最后一段
    res += tr.query(1, 1, n, dfn[x], dfn[y]);
    return res;
}

// 子树修改
void update_subtree(int x, ll v) {
    // 直接操作区间 [dfn[x], dfn[x] + siz[x] - 1]
    tr.update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, v);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 初始化树剖
    dfs1(1, 0);
    dfs2(1, 1);
    
    // 建线段树
    tr.build(1, 1, n);

    while (m--) {
        int op, x;
        ll a;
        scanf("%d", &op);
        if (op == 1) { // 单点加
            scanf("%d%lld", &x, &a);
            tr.update(1, 1, n, dfn[x], dfn[x], a);
        } else if (op == 2) { // 子树加
            scanf("%d%lld", &x, &a);
            update_subtree(x, a); // 直接调用子树修改函数
        } else { // 路径查
            scanf("%d", &x);
            printf("%lld\n", query_path(x, 1)); // 查 x 到 根(1)
        }
    }

    return 0;
}

两种方法的对比总结

针对 Luogu P3178 这道题：

维度	树剖 (HLD) + 线段树	DFS序 + 树状数组 (贡献法)
思维难度	低。这是标准模板题，不需要脑筋急转弯。	高。需要推导数学公式 ( $dep$ 系数)。
代码量	大。需要写 DFS1, DFS2, 线段树 Build, Update, Query。	小。只需要 DFS, 两个简单的 BIT。
通用性	强。如果题目要把“路径求和”改成“路径最大值”，树剖改一行代码即可；贡献法直接失效。	弱。严重依赖“求和”这种可差分、可拆解的性质。
时间复杂度	$O(M \log^2 N)$ (因为要跳链)。	$O(M \log N)$ (只有树状数组操作)。

结论：

比赛策略：如果只是简单的求和，用 DFS序 + 树状数组 写得快且常数小（前提是你推得出来公式）。
通用策略：如果不确定后面会不会有骚操作（比如求 max, min），或者不想推公式，树剖是最稳健的选择。