树上路径处理

给一整棵子树加上一个数，你准备怎么改？如果要问两点之间的距离，是不是每次都沿着树爬一遍？

树上的关系看着不像数组那么整齐，但我们手里已经有不少工具了。这节课我们要做三件事：把子树“拍扁”成一段区间，用倍增找到路径转弯的枢纽，再把整条路径的修改压缩成几个标记。

学完这套组合拳，遇到复杂的树上操作，你就能直接降维打击，套用线段树或树状数组。

一、降维打击：用 DFS 序把树“拍扁”

树形结构难处理，是因为它分叉。我们能不能把它拉直，变成我们最熟悉的一维数组？

场景：有一棵 7 个节点的树，以 1 为根。

         1
       /   \
      2     3
     / \     \
    4   5     6
         \
          7

按照深度优先搜索 (DFS) 的规矩，一条路走到黑。访问顺序是：$1,2,4,5,7,3,6$。 注意：节点编号和访问顺序不是同一个东西。节点 4 是第 3 个被访问的，所以它打卡的时间戳 dfn[4] = 3。

我们定义几个“灵魂数组”：

• dep[u]：节点的深度。
• sz[u]：以 $u$ 为根的子树里一共包含了多少个节点。
• dfn[u]：第一次走到这个点时，给它发的编号（时间戳）。

1. 为什么子树恰好是一段连续区间？

问一个极其核心的问题：DFS 进入节点 2 以后，会不会搜到一半，突然跑去访问节点 3？

绝对不会。它一定先把 2 这一家的点全部搜完，才退回 1，轮到下一家。于是，2 的子树 $\{2,4,5,7\}$ 连着拿走了第 2、3、4、5 个编号，中间没有任何外人插队！

第一个编号是 dfn[u]，整个家族一共占了 sz[u] 个位置。这就意味着，整棵子树被完美地映射到了一个连续的一维区间：

拿节点 5 验算一下：dfn[5] = 4，sz[5] = 2，对应区间 $[4,5]$，恰好装下了节点 5 和 7。

这下彻底打通了老工具的任督二脉：

• 修改一个节点 $u$：直接修改数组里的 dfn[u] 位置。
• 查询子树 $u$ 的和：查询数组区间 $[dfn[u], dfn[u]+sz[u]-1]$。
• 给子树 $u$ 统一加数：给这个区间加上一个数。

树状数组和线段树根本不需要知道原来长着一棵树，它们只管维护这个拍扁后的数组。

2. 核心模板：显式栈求 DFS 序

虽然递归 DFS 很好写，但在极端情况下，树可能退化成一条长链，导致深层递归爆栈。这里给出一个用显式栈迭代遍历的写法，作为底层保障。

// 预处理片段，假设 node 是建好的无向树邻接表，tot 为计数器
const int N = 500005;
vector<int> node[N];
int par[N], dep[N], dfn[N], sz[N], ord[N], tot;

void build_dfn(int root) {
    stack<int> st;
    st.push(root);
    dep[root] = 1;
    
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        
        dfn[u] = ++tot;
        ord[tot] = u;    // 记录第 tot 个被访问的节点是谁
        sz[u] = 1;       // 自己先占 1 个位置
        
        // 逆序压栈：为了让邻接表靠前的孩子先出栈（先被访问）
        for (int i = (int)node[u].size() - 1; i >= 0; i--) {
            int v = node[u][i];
            if (v == par[u]) continue; // 不回头走父亲
            
            par[v] = u;
            dep[v] = dep[u] + 1;
            st.push(v);
        }
    }
    
    // 倒着扫一遍 ord 数组，孩子把自己的 size 汇总给父亲
    for (int i = tot; i >= 2; i--) {
        int u = ord[i];
        sz[par[u]] += sz[u];
    }
}

最后这个倒着扫的循环非常精妙。因为出栈晚的（后代）必定在 ord 的后面，倒着扫天然满足了“先算孩子，再算父亲”的拓扑依赖。

二、路径在哪里转弯：倍增求 LCA

在树上，从节点 4 走到节点 7，路径是 $4 \to 2 \to 5 \to 7$。 这条路先向上爬，再向下走，中间转弯的枢纽是节点 2。我们称 2 为 4 和 7 的 最近公共祖先 (Lowest Common Ancestor, 简称 LCA)。

如果每次询问两点之间的路径，都傻傻地一步步往上爬去找交点，遇到长链直接退化成 $O(N)$，妥妥超时。我们要引入“倍增”的思想，进行指数级的跳跃。

1. 灵魂数组：fa[k][u] 存什么？

定义 fa[k][u] 表示：从节点 $u$ 开始，向上走 $2^k$ 步到达的祖先节点。超出树根的部分统统记为 0。

这正是《倍增思想》中的跳转表：把“走到下一个位置”换成“走到父亲”，二进制拆分的方法不变。

如果我想往上跳 8 步，可以拆分成：先跳 4 步，再从那个位置继续跳 4 步。物理意义直接翻译成转移方程：

2. LCA 求解两步走

第一步：先站到同一层 如果两点深度不同，贸然一起起跳，高度差会一直存在，永远遇不到。 比如求 lca(7, 4)，深度分别是 4 和 3。先让较深的 7 往上跳一步到达 5。现在问题变成了求同一层的 5 和 4 的 LCA。

第二步：为什么“祖先不同才跳，相同反而不跳”？ 这一步是初学者最容易凭直觉写反的地方：不是在找公共祖先吗，看见他俩祖先相同，直接跳过去不行吗？ 绝对不行！ 因为公共祖先不止一个。LCA 的父亲、爷爷全都是公共祖先。如果你一大步直接跳到了树根（那是所有人的公共祖先），你就把真正的“最近”公共祖先远远甩在了身后。

所以我们反其道而行之：只要跳完之后，两点还不重合，说明还没到 LCA，可以放心大胆地跳！

if (fa[k][u] != fa[k][v]) {
    u = fa[k][u];
    v = fa[k][v];
}

从大步长到小步长依次尝试，跳到最后，两人一定停在 LCA 的正下方（下一层）。最后再往上走一步 fa[0][u]，就是真正的 LCA。

3. 实战代码：洛谷 P3379 【模板】最近公共祖先

协议约定：输入 $N, M, S$，表示节点数、询问数和根节点。接着 $N-1$ 条无向树边，再给 $M$ 次查询。数据范围 $N \le 5\times 10^5$。 避坑警告：习惯使用 #define int long long 的同学注意，这里开个 $21 \times 500005$ 的大数组，如果强行展开成 long long 会带来不必要的内存压力。祖先存的仅仅是节点编号，我们显式保留 32 位 int32_t。

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

const int N = 500005, LOG = 20;
vector<int> node[N];

// 明确使用 32 位整型，防止大数组 MLE
int32_t fa[LOG + 1][N];
int32_t dep[N], q[N]; 

// 使用 BFS 预处理，不仅防爆栈，还能顺手把层序遍历队列 q 留给后面的差分用
void bfs(int root) {
    int head = 1, tail = 0;
    q[++tail] = root;
    dep[root] = 1;
    
    while (head <= tail) {
        int u = q[head++];
        
        // 自己的层数已定，计算自己的 2^k 祖先
        for (int k = 1; k <= LOG; k++) {
            fa[k][u] = fa[k - 1][fa[k - 1][u]];
        }
        
        for (int i = 0; i < node[u].size(); i++) {
            int v = node[u][i];
            if (v == fa[0][u]) continue; // 不往回走
            
            fa[0][v] = u;
            dep[v] = dep[u] + 1;
            q[++tail] = v;
        }
    }
}

int query_lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v); // 强制让 u 是较深的那个
    
    // 1. 先跳到同一层
    for (int k = LOG; k >= 0; k--) {
        if (dep[u] - (1 << k) >= dep[v]) {
            u = fa[k][u];
        }
    }
    if (u == v) return u; // 如果已经相遇，说明一个是另一个的祖先
    
    // 2. 两人同步向上逼近
    for (int k = LOG; k >= 0; k--) {
        if (fa[k][u] != fa[k][v]) {
            u = fa[k][u];
            v = fa[k][v];
        }
    }
    // 最后停在 LCA 的正下方，再走一步就是 LCA
    return fa[0][u]; 
}

void solve() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    
    bfs(s);
    
    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << query_lca(u, v) << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

三、树上距离计算：减掉重复走的那一段

知道 LCA 之后，求两点距离就成了 $O(1)$ 的数学游戏。

记 $p = \text{lca}(u, v)$。 从根走到 $u$，再从根走到 $v$，这两条路都包含了从“根到 $p$”的这一段。我们真正想要的距离，只是底下的两条分支。 所以，把两者的深度加起来，再把公共部分减掉两遍即可：

带权树怎么办？只要再维护一个 dist[u] 表示根到 $u$ 的边权和即可，公式完全一样：

四、树上差分：修改整条路径，能不能只动几个位置？

场景：给 $M$ 条路径，每次要把路径上的所有点的值都 $+1$。最后问每个点被经过了多少次。 如果每次都顺着树爬一遍，最坏情况复杂度是 $O(N \cdot M)$。

回想一维数组的区间加法，我们用差分只修改两头，最后再求一次前缀和。 树上路径也可以差分！只不过，贡献不是从左往右流，而是从叶子向根节点（自底向上）汇总。

1. 点差分：LCA 自己要留一份

先在路径的两端 $u$ 和 $v$ 各种下一份 $+1$。如果一直往上汇总，这两笔贡献都会一路流到树根。 当这两股力量在 $p = \text{lca}(u,v)$ 相遇时，$p$ 拿到了两份。可是 $p$ 只是路径上的一个点，它只该拿一份。怎么办？

• 在 $p$ 扣掉一份：现在 $p$ 正常了，但剩下的一份还会继续往上流窜。
• 在 $p$ 的父亲扣掉一份：这下刚好把多余的贡献彻底拦住！

int p = query_lca(u, v);
d[u]++;
d[v]++;
d[p]--;
d[fa[0][p]]--;

拿路径 $4 \to 7$ 手推一下：在 4 和 7 各 $+1$，在 2 (LCA) 和 1 (LCA 的父亲) 各 $-1$。从下往上结算时：

• 节点 4, 7：拿到自己身上的 $+1$ = 1
• 节点 5：收到 7 的 $+1$ = 1
• 节点 2：收到 4 的 $+1$ 和 5 传上来的 $+1$，加上自己身上的 $-1$，结果 $= 1+1-1 = 1$
• 节点 1：收到 2 传上来的 $+1$，加上自己身上的 $-1$，结果 $= 1-1 = 0$

只有 $4, 2, 5, 7$ 留下了 1，不多不少，完美覆盖路径！

2. 边差分：LCA 向上的边不能留

如果是给路径上的“边”加权呢？ 常规套路：把边的权值存在它较深的那个端点上。即 d[x] 记录的是节点 $x$ 到它父亲的那条边。

当 $u$ 和 $v$ 的贡献到达 $p$ (LCA) 时，整条路径已经走完了！路径根本没有经过 $p$ 向上通往父亲的那条边。 所以这两份贡献在 $p$ 这里必须被全额剿灭，直接扣掉 2 份：

int p = query_lca(u, v);
d[u]++;
d[v]++;
d[p] -= 2;

区别死死卡在“LCA 自己到底要不要保留”：点差分要保留这个点，扣 1；边差分不保留向上的边，扣 2。

3. 如何汇总？反转 BFS 序列！

怎么做到“自底向上，先算孩子再算父亲”？ 还记得我们在前面 LCA 模板里存下的 q 数组吗？那是 BFS 层序遍历的顺序。入队时父亲在前、孩子在后。 只要倒着遍历 BFS 队列，轮到某个点的时候，它的所有孩子一定已经把结果上交完毕了！

4. 核心模板：点差分统计节点经过次数

协议约定：输入 $N, M$，表示节点数和路径数。接着 $N-1$ 条无向树边，再给出 $M$ 条路径。最后输出节点 1 到 $N$ 各自被经过的次数。 数据范围 $1 \le N \le 5\times 10^5$，$0 \le M \le 5\times 10^5$。

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

const int N = 500005, LOG = 20;
vector<int> node[N];
int32_t fa[LOG + 1][N], dep[N], q[N], d[N];

void bfs(int root) {
    int head = 1, tail = 0;
    q[++tail] = root;
    dep[root] = 1;
    while (head <= tail) {
        int u = q[head++];
        for (int k = 1; k <= LOG; k++) {
            fa[k][u] = fa[k - 1][fa[k - 1][u]];
        }
        for (int i = 0; i < node[u].size(); i++) {
            int v = node[u][i];
            if (v == fa[0][u]) continue;
            fa[0][v] = u;
            dep[v] = dep[u] + 1;
            q[++tail] = v;
        }
    }
}

int query_lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int k = LOG; k >= 0; k--) {
        if (dep[u] - (1 << k) >= dep[v]) u = fa[k][u];
    }
    if (u == v) return u;
    for (int k = LOG; k >= 0; k--) {
        if (fa[k][u] != fa[k][v]) {
            u = fa[k][u];
            v = fa[k][v];
        }
    }
    return fa[0][u];
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    
    bfs(1);
    
    // 读入 M 条路径，打上差分标记
    while (m--) {
        int u, v;
        cin >> u >> v;
        int p = query_lca(u, v);
        
        d[u]++;
        d[v]++;
        d[p]--;
        d[fa[0][p]]--; // 扣除 LCA 父亲的贡献
    }
    
    // 灵魂一步：倒序遍历 BFS 队列，把孩子的贡献累加给父亲
    for (int i = n; i >= 2; i--) {
        int u = q[i];
        d[fa[0][u]] += d[u];
    }
    
    for (int u = 1; u <= n; u++) {
        cout << d[u] << (u == n ? "" : " ");
    }
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

把所有的修改离线存下来，最后 $O(N)$ 统一汇总。这种极其优美的解法，不仅节省了大量时间，还能让你在面对更复杂的树上操作时游刃有余。

五、树上路径再探：往上走 K 步与路径上的第 K 个点

刚才我们用倍增找出了两个点的 LCA。但倍增数组 fa[k][u] 的威力远不止于此，它天生就是用来解决“跳跃”问题的。

1. 怎么快速找到往上走 K 步后的节点？

场景：从节点 $u$ 出发，往上走 $K$ 步，到达的祖先是谁？ 如果一步步往上爬，最坏情况要走 $O(N)$。但有了倍增数组，我们可以像拼凑二进制数一样跳跃。

比如 $K = 5$，它的二进制是 $101_2$，也就是 $5 = 4 + 1$。 我们先让 $u$ 往上跳 $2^2 = 4$ 步，到达 $u'$，然后再从 $u'$ 往上跳 $2^0 = 1$ 步，就准确到达了从 $u$ 往上走 5 步的位置。

代码实现： 沿用前面预处理的 fa、dep 和 LOG，约定 $k\ge0$。根的深度是 1，所以往上最多走 dep[u]-1 步；超过这个步数就返回 0，走 0 步则仍是自己。

int get_kth_ancestor(int u, int k) {
    if (k >= dep[u]) return 0;
    for (int i = LOG; i >= 0; i--) {
        if ((k >> i) & 1) { // 如果 k 的二进制第 i 位是 1
            u = fa[i][u];
        }
    }
    return u;
}

这段代码直接把 $k$ 的二进制位拆开，哪位有 1 就往上跳 $2^i$ 步。

2. 路径上的第 K 个点

场景：我想知道从节点 $u$ 走到节点 $v$ 的最短路径上，第 $K$ 个经过的点是谁？（规定 $u$ 是第 1 个点）

这条路一定是通过 $p = \text{lca}(u,v)$ 转弯的。我们把路拆成两半：上升段（$u \to p$）和下降段（$p \to v$）。

1. 先算算上升段有多长：$d_1 = dep[u] - dep[p]$。从 $u$ 走到 $p$ 一共包含了 $d_1 + 1$ 个点。
2. 如果在上升段：如果 $K \le d_1 + 1$，说明我们要找的点还没越过枢纽 $p$。它就是从 $u$ 往上走 $K-1$ 步到达的节点。直接调用 get_kth_ancestor(u, K - 1) 即可。
3. 如果在下降段：如果 $K > d_1 + 1$，说明点已经翻过 $p$，在往 $v$ 下降的半坡上。这时从 $u$ 正向推算很难，我们反过来从 $v$ 往上找。 整条路径的边数是 $d_1 + d_2$（其中 $d_2 = dep[v] - dep[p]$），总点数是 $d_1 + d_2 + 1$。正数第 $K$ 个点，倒数过来就是第 $(d_1 + d_2 + 1) - K + 1$ 个点，也就是从 $v$ 往上走 $d_1 + d_2 + 1 - K$ 步到达的节点。

手推验证：$u$ 到 $p$ 距离 $d_1=3$，$p$ 到 $v$ 距离 $d_2=4$。路径总共 8 个点。 要求第 6 个点。它在下降段。倒数过来，它是从 $v$ 往上走 $3 + 4 + 1 - 6 = 2$ 步到达的节点。刚好是正确的！

六、选学：动态换根 LCA——到底是谁当了枢纽？

场景：有一棵树，本来以 1 为根。现在系统动态发号施令：“如果此时把根换成 $R$，节点 $u$ 和 $v$ 的 LCA 是谁？” 换根询问会给出多次，如果每次都重新跑一遍 BFS 预处理倍增数组，必定超时。

其实原树的结构并没有被破坏，我们根本不需要重新建树。 在以原根（设为 1）为基础的树中，新 LCA 的答案必定只在三个点中产生：

1. $p_1 = \text{lca}(u, v)$
2. $p_2 = \text{lca}(u, R)$
3. $p_3 = \text{lca}(v, R)$

这三个候选点全部在原树里用 $O(\log N)$ 算出来。这三者中，在原树里深度最深（即 dep 最大）的那个，就是新根 $R$ 下的 LCA！

物理直觉： 把 $R\to u$ 和 $R\to v$ 两条路画出来：它们从 $R$ 出发，先走同一段，再在某个点分开。这个分叉点就是新根下的 LCA，也同时在 $u\to v$ 的路径上。再按原根看三个候选，其中至少两个重合，剩下的那个不会更浅；取深度最大者，恰好就是这个分叉点。换的是观察树的方向，不是把候选点重新提成根。

实战验证程序： 数据范围：$N \le 10^5, M \le 10^5$。每次询问给出新根 $R$ 和节点 $u, v$。

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

const int N = 100005, LOG = 18;
vector<int> node[N];
int32_t fa[LOG + 1][N], dep[N], q[N];

void bfs(int root) {
    int head = 1, tail = 0;
    q[++tail] = root;
    dep[root] = 1;
    fa[0][root] = 0;
    
    while (head <= tail) {
        int u = q[head++];
        for (int k = 1; k <= LOG; k++) {
            fa[k][u] = fa[k - 1][fa[k - 1][u]];
        }
        for (int i = 0; i < node[u].size(); i++) {
            int v = node[u][i];
            if (v == fa[0][u]) continue;
            fa[0][v] = u;
            dep[v] = dep[u] + 1;
            q[++tail] = v;
        }
    }
}

int query_lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int k = LOG; k >= 0; k--) {
        if (dep[u] - (1 << k) >= dep[v]) u = fa[k][u];
    }
    if (u == v) return u;
    for (int k = LOG; k >= 0; k--) {
        if (fa[k][u] != fa[k][v]) {
            u = fa[k][u];
            v = fa[k][v];
        }
    }
    return fa[0][u];
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    
    bfs(1); // 永远以 1 为原树的根进行一次预处理
    
    while (m--) {
        int r, u, v;
        cin >> r >> u >> v;
        int p1 = query_lca(u, v);
        int p2 = query_lca(u, r);
        int p3 = query_lca(v, r);
        
        // 选出三者中在原树深度最深的点
        int ans = p1;
        if (dep[p2] > dep[ans]) ans = p2;
        if (dep[p3] > dep[ans]) ans = p3;
        cout << ans << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}
/*
【输入样例】
5 3
1 2
1 3
2 4
2 5
2 4 5
4 4 5
3 4 5

【输出样例】
2
4
2
*/

七、在线修改的抉择：单点修改与路径求和

前面学的树上差分是离线的——必须把所有的加法标记打完，最后从底向上一次性算清。如果题目要求“改一次，查一次”这种在线操作呢？

我们手里的武器是 DFS 序，它能把子树变成一维数组的连续区间。

1. 子树修改与子树求和

这个最简单。既然子树是一段连续区间 $[dfn[u], dfn[u]+sz[u]-1]$，那这就是纯粹的“一维数组区间修改、区间求和”。直接套一个线段树或者两个树状数组就能解决。

2. 单点修改与路径求和

场景：每次修改某个节点 $u$ 的权值（加上 $x$），随时查询从 $u$ 到 $v$ 路径上的点权和。

如果硬要去更新路径，你会发现路径在 DFS 序上是被打断成好几截的。我们转变思路，维护每个点到根节点的路径和 sum[x]。 任意两点 $u$ 到 $v$ 的路径权值和公式可以写为：$sum[u] + sum[v] - 2 \times sum[\text{lca}(u,v)] + val[\text{lca}(u,v)]$。

那么，当我给点 $u$ 的自身权值 $val[u]$ 加上 $x$ 时，谁的 sum 会受到影响？ 只有在 $u$ 的子树里的所有节点，它们到根的路径必定经过 $u$。 于是，“单点修改”被巧妙转化成了“把 $u$ 子树内所有点的 sum 统一加上 $x$”。 结合 DFS 序，这变成了：区间加法，单点查询！一个最基础的树状数组就能搞定。

3. 树链剖分的前奏

如果既要“在线修改整条路径”，又要“随时查询整条路径”呢？ 这就超出了 DFS 序和倍增的管辖范围。我们要查的路径在数组里七零八落，怎么办？

我们需要一种技术：沿着树的重力方向，把树切成一条条笔直的“链”。使得任意两点间的路径，都能被拼凑成极少段在数组里连续的区间。 只要能切成连续区间，就能无缝扔进线段树里维护。这就是树链剖分，本套不展开，作为后续拓展方向。

八、实战练习题单

1. 洛谷 P3379 【模板】最近公共祖先
   • 训练指引：先独立手敲一遍 LCA。跟自己解释清楚代码里“不相同才跳”的逻辑，比把代码背下来重要得多。
2. 极端数据自测
   • 自己造几组小数据测试：只有一个点的情况；路径两端相同；一端是另一端的祖先；LCA 恰好是树根。用这些边界情况检查你的点差分和边差分是否写错。
3. 洛谷 P3128 [USACO15DEC] Max Flow P
   • 训练指引：最纯正的树上点差分模板题。跑完差分后不再是输出每个点，而是扫一遍数组取个最大值。别被名字里的 Flow 骗去写网络流了。

当你下次遇到子树修改，第一反应应该是“DFS 序拍扁”；遇到路径问题，先找 LCA 拆分；需要反复在路径上加加减减，把树上差分掏出来。工具没有变多难，只是现在，你终于把它们接起来了。