树形 DP：换根、虚树与树上背包

树是竞赛与工程中出现频率极高的数据结构。在树上做动态规划——树形 DP——是一种”结构即顺序”的范式：树本身提供了天然的拓扑序，子问题之间的依赖关系清晰而优美。本文将从最基础的自底向上模型出发，逐步深入到换根 DP、虚树优化、树上背包与点分治，力求在理论推导与工程实现之间取得平衡。

一、树形 DP 基础：子树即子问题

1.1 核心思想

树形 DP 的核心思想非常直观：将每棵子树视为一个子问题。对于以节点 \(u\) 为根的子树，我们首先递归地求解其所有子节点 \(v\) 对应的子问题，然后将子节点的答案合并到 \(u\)。这种”自底向上”的计算顺序等价于后序遍历（post-order traversal）。

设 \(dp[u]\) 表示以 \(u\) 为根的子树上某种信息，状态转移的一般形式为：

\[dp[u] = \bigoplus_{v \in \text{children}(u)} f(dp[v])\]

其中 \(\bigoplus\) 是某种合并操作（求和、取最值、卷积等），\(f\) 是从子节点到父节点的转移函数。

1.2 最简单的例子：子树大小

int sz[MAXN];

void dfs(int u, int fa) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

这段代码在 \(O(n)\) 时间内算出每个节点的子树大小。看似平淡无奇，但它是后面所有复杂技巧的起点。

1.3 经典模型：树的最大独立集

给定一棵 \(n\) 个节点的树，每个节点有权值 \(w[u]\)，选出一个节点子集使得没有两个相邻节点同时被选中，最大化权值和。

定义 \(dp[u][0/1]\)：以 \(u\) 为根的子树中，\(u\) 不选/选时的最大权值和。

\[dp[u][0] = \sum_{v \in \text{children}(u)} \max(dp[v][0], dp[v][1])\]

\[dp[u][1] = w[u] + \sum_{v \in \text{children}(u)} dp[v][0]\]

long long dp[MAXN][2];

void dfs(int u, int fa) {
    dp[u][0] = 0;
    dp[u][1] = w[u];
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

答案为 \(\max(dp[\text{root}][0], dp[\text{root}][1])\)。时间复杂度 \(O(n)\)。

1.4 实现细节

几个容易忽视的要点：

无根树的处理：通常任选一个节点作为根，DFS 时通过记录父节点 fa 来避免走回头路。
栈溢出：当树退化为链时，递归深度可达 \(n\)。如果 \(n \geq 10^5\)，需要手动设置栈大小或改用非递归写法。
邻接表与数组清空：多组数据时，只清空访问过的节点，不要暴力 memset 整个数组。

二、换根 DP（Rerooting）

2.1 问题引入：树上距离和

给定一棵 \(n\) 个节点的无权树，对每个节点 \(u\)，求所有其它节点到 \(u\) 的距离之和 \(\text{ans}[u]\)。

朴素做法：以每个节点为根做一次 DFS，\(O(n^2)\)。当 \(n\) 达到 \(10^5\) 甚至 \(10^6\) 时，这是不可接受的。

换根 DP 的思路是：先固定一个根求出答案，再通过”换根”的代数关系推导出其它所有根的答案，总复杂度 \(O(n)\)。

2.2 两次 DFS 框架

第一次 DFS（自底向上）：以节点 1 为根，计算两个数组：

\(sz[u]\)：以 \(u\) 为根的子树大小。
\(dp[u]\)：子树内所有节点到 \(u\) 的距离之和。

转移方程：

\[dp[u] = \sum_{v \in \text{children}(u)} (dp[v] + sz[v])\]

直觉：子树 \(v\) 中每个节点到 \(v\) 的距离之和为 \(dp[v]\)，而从 \(v\) 到 \(u\) 还要多走一步，所以再加 \(sz[v]\)。

第二次 DFS（自顶向下）：从根开始，将答案从父节点”推”到子节点。

当我们将根从 \(u\) 换到其子节点 \(v\) 时： - \(v\) 的子树中的 \(sz[v]\) 个节点，各少走一步，贡献减少 \(sz[v]\)。 - 不在 \(v\) 子树中的 \(n - sz[v]\) 个节点，各多走一步，贡献增加 \(n - sz[v]\)。

因此：

\[\text{ans}[v] = \text{ans}[u] - sz[v] + (n - sz[v]) = \text{ans}[u] + n - 2 \cdot sz[v]\]

2.3 完整实现

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

const int MAXN = 500005;
vector<int> adj[MAXN];
long long dp[MAXN], ans[MAXN];
int sz[MAXN];
int n;

// 第一次 DFS：自底向上，计算 dp[u] 和 sz[u]
void dfs1(int u, int fa) {
    sz[u] = 1;
    dp[u] = 0;
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        dp[u] += dp[v] + sz[v];
    }
}

// 第二次 DFS：自顶向下，利用父节点答案推导
void dfs2(int u, int fa) {
    for (int v : adj[u]) {
        if (v == fa) continue;
        ans[v] = ans[u] + n - 2 * sz[v];
        dfs2(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs1(1, 0);
    ans[1] = dp[1];
    dfs2(1, 0);

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    }
    return 0;
}

2.4 一般化的换根 DP 框架

不是所有问题都像距离和那样有简洁的换根公式。更一般地，设信息的合并操作为 \(\oplus\)，从子到父的转移为 \(f\)，换根时需要”去掉某个子树的贡献”。如果 \(\oplus\) 存在逆运算（如加法对应减法），可以直接减去；否则需要用前缀/后缀合并来避开逆运算。

// 对于不可逆的合并操作，使用前缀/后缀数组
void dfs2(int u, int fa) {
    int deg = adj[u].size();
    // prefix[i] = f(dp[child_0]) ⊕ ... ⊕ f(dp[child_{i-1}])
    // suffix[i] = f(dp[child_i]) ⊕ ... ⊕ f(dp[child_{deg-1}])
    vector<Info> prefix(deg + 1, identity), suffix(deg + 1, identity);

    vector<int> children;
    for (int v : adj[u]) {
        if (v != fa) children.push_back(v);
    }
    int m = children.size();
    for (int i = 0; i < m; i++) {
        prefix[i + 1] = merge(prefix[i], f(dp[children[i]]));
    }
    for (int i = m - 1; i >= 0; i--) {
        suffix[i] = merge(f(dp[children[i]]), suffix[i + 1]);
    }

    for (int i = 0; i < m; i++) {
        int v = children[i];
        // u 去掉子树 v 后的贡献 = parent_contrib ⊕ prefix[i] ⊕ suffix[i+1]
        Info without_v = merge(parent_info[u], merge(prefix[i], suffix[i + 1]));
        // 用 without_v 推导 v 作为根时的答案
        ans[v] = combine(dp[v], without_v);
        parent_info[v] = g(without_v);
        dfs2(v, u);
    }
}

2.5 换根 DP 的另一个经典例题：树的直径端点

对每个节点 \(u\)，求距离 \(u\) 最远的节点的距离。这等价于先求树的直径，答案一定在直径的两个端点之一取到。不过用换根 DP 同样可以优雅地解决。

定义 \(dp[u]\)：以 \(u\) 为根的子树中，\(u\) 到子树内最远节点的距离。第二次 DFS 时需要从父节点传下来”父方向上的最远距离”。这里需要维护子节点中最大和次大两个值，以处理最大值恰好来自当前子树的情况。

int dp[MAXN];     // 子树内最远距离
int dp2[MAXN];    // 子树内次远距离（经过不同子节点）
int up[MAXN];     // 向父方向的最远距离

void dfs1(int u, int fa) {
    dp[u] = dp2[u] = 0;
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        int d = dp[v] + 1;
        if (d >= dp[u]) {
            dp2[u] = dp[u];
            dp[u] = d;
        } else if (d > dp2[u]) {
            dp2[u] = d;
        }
    }
}

void dfs2(int u, int fa) {
    for (int v : adj[u]) {
        if (v == fa) continue;
        // 如果 u 的最远距离来自 v 的子树，则用次远距离
        if (dp[v] + 1 == dp[u]) {
            up[v] = max(up[u], dp2[u]) + 1;
        } else {
            up[v] = max(up[u], dp[u]) + 1;
        }
        dfs2(v, u);
    }
}

最终每个节点 \(u\) 的答案为 \(\max(dp[u], up[u])\)。

三、虚树（Auxiliary Tree / Virtual Tree）

3.1 问题背景

考虑这样一类问题：一棵 \(n\) 个节点的树，\(q\) 次查询，每次查询给出一组关键点 \(S_i\)（\(|S_i| = k_i\)），要求在树上对这些关键点做某种 DP 或统计。

朴素做法：每次查询都在整棵树上 DFS，总复杂度 \(O(nq)\)。当 \(\sum k_i\) 远小于 \(nq\) 时，这极其浪费。

虚树的核心思想：对于每次查询，只保留关键点及它们之间的 LCA 节点，构建一棵大小为 \(O(k_i)\) 的”压缩树”，然后在这棵小树上做 DP。总复杂度降为 \(O(n \log n + \sum k_i \log k_i)\)（预处理 + 所有查询）。

3.2 虚树的构造

构造虚树的步骤如下：

预处理：对原树做 DFS，记录 DFS 序 \(\text{dfn}[u]\)，并预处理 LCA（倍增或 Tarjan）。
排序：将关键点按 DFS 序排序。
补充 LCA：相邻关键点之间的 LCA 也可能是虚树上的分叉点，需要加入。
用栈构建：维护一条从根到当前节点的链，模拟 DFS 的过程。

// 虚树构造
// 前置：dfn[], lca(u,v), 以及原树的边权信息

bool cmp_dfn(int a, int b) { return dfn[a] < dfn[b]; }

// stk 模拟从根到当前节点的链
int stk[MAXN], top;
vector<int> vt_adj[MAXN]; // 虚树的邻接表

void add_edge(int u, int v) {
    vt_adj[u].push_back(v);
}

void insert(int u) {
    if (top == 0) {
        stk[++top] = u;
        return;
    }
    int l = lca(u, stk[top]);
    if (l != stk[top]) {
        // 弹出栈中在 l 之下的节点，连边
        while (top > 1 && dfn[stk[top - 1]] >= dfn[l]) {
            add_edge(stk[top - 1], stk[top]);
            top--;
        }
        if (stk[top] != l) {
            add_edge(l, stk[top]);
            stk[top] = l;
        }
    }
    stk[++top] = u;
}

void build_virtual_tree(vector<int>& keys) {
    sort(keys.begin(), keys.end(), cmp_dfn);
    // 去重
    keys.erase(unique(keys.begin(), keys.end()), keys.end());

    top = 0;
    // 确保根节点在虚树中
    if (keys.empty() || keys[0] != 1) {
        stk[++top] = 1;
    }

    for (int u : keys) {
        insert(u);
    }
    // 弹出栈中剩余节点
    while (top > 1) {
        add_edge(stk[top - 1], stk[top]);
        top--;
    }
}

3.3 虚树的大小分析

虚树中的节点数不超过 \(2k - 1\)，其中 \(k\) 是关键点数量。证明如下：

关键点按 DFS 序排列为 \(a_1, a_2, \ldots, a_k\)。
虚树中除了这 \(k\) 个关键点外，还包含相邻关键点的 LCA，最多 \(k - 1\) 个（有些 LCA 可能重复或本身就是关键点）。
因此虚树总节点数 \(\leq 2k - 1\)。

3.4 典型应用

虚树最常见的使用场景：

多次查询的树形 DP：每次只关心少量关键点，在虚树上做 DP。
Steiner 树问题：连接给定关键点的最小权连通子图。
树上关键点的连通性：判断关键点之间的路径关系。

3.5 虚树上的 DP 示例

问题：给定树上 \(k\) 个关键点，求连接所有关键点的最小边权和（即 Steiner 树的一个特殊情况）。

// 在虚树上做 DP
// dist(u, v) 为原树中 u 到 v 的距离（预处理）
long long solve_on_virtual_tree(int root) {
    long long total = 0;
    function<void(int)> dfs = [&](int u) {
        for (int v : vt_adj[u]) {
            dfs(v);
            total += dist(u, v); // 原树上 u 到 v 的距离
        }
    };
    dfs(root);
    return total;
}

虚树构建后一定记得清空邻接表（只清访问过的节点）：

void clear_virtual_tree(int u) {
    for (int v : vt_adj[u]) {
        clear_virtual_tree(v);
    }
    vt_adj[u].clear();
}

四、树上背包

4.1 问题定义

给定一棵 \(n\) 个节点的有根树，每个节点有一个物品（重量 \(w[u]\)，价值 \(v[u]\)），选择节点时要求如果选了 \(u\)，必须选 \(u\) 的父节点（即选出的节点集合构成一棵包含根的连通子树）。在总重量不超过 \(m\) 的约束下，最大化价值。

这是有依赖的背包问题在树上的自然推广。

4.2 朴素做法：O(n * m^2)

对每个节点 \(u\)，维护 \(dp[u][j]\) 表示在以 \(u\) 为根的子树中选择总重量恰好为 \(j\) 的最大价值。合并子节点 \(v\) 时：

\[dp[u][j] = \max_{0 \leq k \leq j} (dp[u][j - k] + dp[v][k])\]

这实际上是对每个子节点做一次分组背包（卷积），复杂度分析如下：

对于节点 \(u\) 和子节点 \(v\)，卷积的代价为 \(O(sz[u'] \cdot sz[v])\)，其中 \(sz[u']\) 是合并到 \(v\) 之前 \(u\) 的已知子树大小。
朴素实现：不加控制地枚举到 \(m\)，每条边贡献 \(O(m)\) 次运算，总复杂度 \(O(nm)\)——等等，这不是 \(O(nm^2)\) 吗？

关键在于枚举上界的控制。

4.3 O(nm) 优化：子树大小约束

核心观察：节点 \(u\) 的子树中最多有 \(sz[u]\) 个物品，所以 \(dp[u][j]\) 只在 \(j \leq \min(sz[u], m)\) 时有意义。

优化实现：合并子节点 \(v\) 到 \(u\) 时，枚举 \(j\) 的范围限制为已合并的子树大小：

void dfs(int u, int fa) {
    sz[u] = 1;
    dp[u][w[u]] = v[u]; // 必须选 u 自己

    for (int child : adj[u]) {
        if (child == fa) continue;
        dfs(child, u);

        // 合并时枚举范围由子树大小决定
        int lim_u = min(sz[u], m);
        int lim_v = min(sz[child], m);

        // 倒序枚举以避免覆盖
        for (int j = lim_u + lim_v; j >= w[u]; j--) {
            for (int k = max(0, j - lim_u); k <= min(j, lim_v); k++) {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[child][k]);
            }
        }
        sz[u] += sz[child];
    }
}

4.4 复杂度分析：为什么是 O(nm)

这是树上背包中最精妙的部分。对于每条树边 \((u, v)\)，合并的代价正比于 \(sz[u'] \cdot sz[v]\)，其中 \(sz[u']\) 是合并 \(v\) 之前 \(u\) 已有的子树大小（包含 \(u\) 自身和之前已合并的子节点）。

总运算量为：

\[T = \sum_{(u,v) \in E} sz[u'] \cdot sz[v]\]

可以证明 \(T \leq nm\)。直觉上，每一对节点 \((a, b)\)（分别在 \(u\) 的已合并部分和 \(v\) 的子树中）在整个过程中恰好被计数一次，而总共的节点对数不超过 \(n \cdot m\)。

更形式化地：考虑树中任意两个节点 \(a\) 和 \(b\)，它们在合并过程中被”配对”的当且仅当它们在合并的瞬间分属不同的子树。每对 \((a, b)\) 恰好在 \(\text{LCA}(a, b)\) 处被计数一次。所有这样的对的数量不超过 \(\binom{n}{2} \leq nm\)（当 \(m \geq n\) 时退化为 \(O(n^2)\)，当 \(m < n\) 时由容量 \(m\) 截断）。

4.5 实现陷阱

初始化：\(dp[u][0]\) 的含义要想清楚——是”不选 \(u\)“还是”空集”？如果必须选根，那 \(dp[u][0]\) 应该设为 \(-\infty\)（不合法）。
合并顺序：倒序枚举 \(j\) 很关键，原理与 01 背包的空间优化一致。
二维数组 vs. 一维滚动：树上背包通常需要真正的二维数组 \(dp[u][\cdot]\)，因为合并时需要同时访问两个子树的信息。如果内存紧张，可以用 DFS 序将节点编号重排，使得同一子树的节点连续存储。

五、点分治（Centroid Decomposition）

5.1 问题引入

给定一棵 \(n\) 个节点的带权树，统计有多少条路径的权值和恰好为 \(k\)。朴素做法 \(O(n^2)\)，点分治可以做到 \(O(n \log n)\)。

点分治的核心：反复找重心，分治处理经过重心的路径。

5.2 重心的性质

树的重心（centroid）\(c\) 满足：删除 \(c\) 后，最大的连通分量大小 \(\leq n/2\)。

寻找重心的算法：

int sz[MAXN], maxp[MAXN];
int centroid, min_maxp;
bool removed[MAXN]; // 标记已被移除的重心

void get_sz(int u, int fa) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v == fa || removed[v]) continue;
        get_sz(v, u);
        sz[u] += sz[v];
    }
}

void get_centroid(int u, int fa, int tree_sz) {
    maxp[u] = 0;
    for (int v : adj[u]) {
        if (v == fa || removed[v]) continue;
        get_centroid(v, u, tree_sz);
        maxp[u] = max(maxp[u], sz[v]);
    }
    maxp[u] = max(maxp[u], tree_sz - sz[u]);
    if (maxp[u] < min_maxp) {
        min_maxp = maxp[u];
        centroid = u;
    }
}

int find_centroid(int u) {
    get_sz(u, 0);
    min_maxp = INT_MAX;
    get_centroid(u, 0, sz[u]);
    return centroid;
}

重心的关键性质保证了分治的层数不超过 \(O(\log n)\)。

5.3 点分治框架

void solve(int u) {
    int c = find_centroid(u);
    removed[c] = true;

    // 处理经过 c 的路径
    calc(c);

    // 递归处理每个子连通分量
    for (int v : adj[c]) {
        if (!removed[v]) {
            solve(v);
        }
    }
}

5.4 处理经过重心的路径

以”路径权值和为 \(k\)“的问题为例：

从重心 \(c\) 出发 DFS，收集每个子树中的所有路径长度。
两条来自不同子树的路径拼接，即可得到经过 \(c\) 的路径。
用排序 + 双指针或哈希表统计答案。

vector<int> paths; // 存储从 c 出发的路径权值

void get_paths(int u, int fa, int dist) {
    paths.push_back(dist);
    for (int v : adj[u]) {
        if (v == fa || removed[v]) continue;
        get_paths(v, u, dist + w[u][v]);
    }
}

long long calc(int c) {
    long long ans = 0;
    vector<int> all_paths;
    all_paths.push_back(0); // c 本身

    for (int v : adj[c]) {
        if (removed[v]) continue;
        paths.clear();
        get_paths(v, c, w[c][v]);

        // 用当前子树的路径与之前子树的路径配对
        // （这里用排序 + 双指针或哈希表）
        for (int d : paths) {
            // 在 all_paths 中查找 k - d
            // 具体实现取决于问题
        }

        for (int d : paths) {
            all_paths.push_back(d);
        }
    }
    return ans;
}

5.5 点分治的复杂度

分治层数：\(O(\log n)\)（因为每层的子问题总大小为 \(n\)，而重心保证每个子问题大小 \(\leq n/2\)）。
每层处理：\(O(n)\)（遍历所有节点）或 \(O(n \log n)\)（如果需要排序）。
总复杂度：\(O(n \log n)\) 或 \(O(n \log^2 n)\)。

六、点分树

6.1 从点分治到点分树

点分治是一种离线算法——在分治过程中一次性处理所有查询。如果需要在线查询（例如带修改的树上路径查询），可以将分治的递归结构显式存储下来，这就是点分树（Centroid Decomposition Tree）。

点分树的构建：在点分治过程中，每次找到重心 \(c\) 后，将 \(c\) 的父节点设为上一层递归的重心。

int ct_fa[MAXN]; // 点分树中的父节点

void build(int u, int father) {
    int c = find_centroid(u);
    ct_fa[c] = father;
    removed[c] = true;

    for (int v : adj[c]) {
        if (!removed[v]) {
            build(v, c);
        }
    }
}

6.2 点分树的性质

深度 \(O(\log n)\)：点分树的深度不超过 \(\lceil \log_2 n \rceil\)。
路径覆盖：原树中任意两点 \(u, v\) 的路径信息可以通过它们在点分树中的 LCA 处查询到。
修改与查询：修改节点 \(u\) 的权值时，沿点分树向上更新 \(O(\log n)\) 个祖先；查询节点 \(u\) 的某种信息时，同样沿点分树向上收集。

6.3 在线查询示例

问题：单点修改权值，查询距节点 \(u\) 不超过 \(d\) 的所有节点的权值和。

思路：对点分树中的每个节点 \(c\)，维护一个数据结构（如 BIT 或 sorted array），记录”\(c\) 管辖范围内所有节点到 \(c\) 的距离”以及对应的权值。修改时沿点分树向上更新；查询时沿点分树向上收集，并减去重复计数。

// 伪代码
long long query(int u, int d) {
    long long ans = 0;
    int cur = u;
    int prev = 0;
    while (cur) {
        int dist_to_ct = dist_in_original_tree(u, cur);
        if (dist_to_ct <= d) {
            // 加上 cur 管辖范围内，距 cur 不超过 d - dist_to_ct 的节点权值和
            ans += cur.data.query(d - dist_to_ct);
            // 减去 prev 子树中已经被 prev 那层计算过的贡献（容斥）
            if (prev) {
                ans -= prev.data_from_parent.query(d - dist_to_ct);
            }
        }
        prev = cur;
        cur = ct_fa[cur];
    }
    return ans;
}

这里的容斥是点分树查询的关键技巧：每个节点维护两份数据——一份是关于自身管辖范围的，一份是关于其在点分树中父节点的管辖范围的，用于去重。

七、完整实现：换根 DP + 虚树 + 点分治

下面给出一个完整的 C++ 实现，涵盖三种核心技术。代码基于一个通用的树结构，依次演示换根 DP（距离和）、虚树构建与查询、以及点分治（路径计数）。

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

// ===================== 基础设施 =====================
const int MAXN = 200005;
const int LOG = 18;

int n;
vector<pair<int, int>> adj[MAXN]; // {邻居, 边权}
int dep[MAXN], fa[MAXN][LOG], dfn[MAXN], timer_dfn;
long long dist_root[MAXN]; // 到根的距离
int sz_all[MAXN];

// ===================== LCA 预处理 =====================
void dfs_lca(int u, int f, int d, long long dd) {
    fa[u][0] = f;
    dep[u] = d;
    dist_root[u] = dd;
    dfn[u] = ++timer_dfn;
    sz_all[u] = 1;
    for (int k = 1; k < LOG; k++) {
        fa[u][k] = fa[fa[u][k - 1]][k - 1];
    }
    for (auto [v, w] : adj[u]) {
        if (v == f) continue;
        dfs_lca(v, u, d + 1, dd + w);
        sz_all[u] += sz_all[v];
    }
}

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

long long dist_tree(int u, int v) {
    return dist_root[u] + dist_root[v] - 2 * dist_root[lca(u, v)];
}

// ===================== 换根 DP：距离和 =====================
namespace Reroot {
    long long dp_down[MAXN], ans[MAXN];
    int sz[MAXN];

    void dfs1(int u, int f) {
        sz[u] = 1;
        dp_down[u] = 0;
        for (auto [v, w] : adj[u]) {
            if (v == f) continue;
            dfs1(v, u);
            sz[u] += sz[v];
            dp_down[u] += dp_down[v] + (long long)sz[v] * w;
        }
    }

    // 带权版本：ans[v] = ans[u] - sz[v]*w + (n - sz[v])*w
    //                    = ans[u] + w*(n - 2*sz[v])
    void dfs2(int u, int f) {
        for (auto [v, w] : adj[u]) {
            if (v == f) continue;
            ans[v] = ans[u] + (long long)w * (n - 2 * sz[v]);
            dfs2(v, u);
        }
    }

    void solve() {
        dfs1(1, 0);
        ans[1] = dp_down[1];
        dfs2(1, 0);

        // ans[u] 即为以 u 为根时的距离和
    }
}

// ===================== 虚树 =====================
namespace VirtualTree {
    vector<int> vt_adj[MAXN];
    int stk[MAXN], top;
    vector<int> nodes_used; // 记录使用过的节点，方便清空

    void add_edge(int u, int v) {
        vt_adj[u].push_back(v);
        nodes_used.push_back(u);
        nodes_used.push_back(v);
    }

    void insert(int u) {
        if (top == 0) {
            stk[++top] = u;
            return;
        }
        int l = lca(u, stk[top]);
        if (l != stk[top]) {
            while (top > 1 && dfn[stk[top - 1]] >= dfn[l]) {
                add_edge(stk[top - 1], stk[top]);
                top--;
            }
            if (stk[top] != l) {
                add_edge(l, stk[top]);
                stk[top] = l;
            }
        }
        stk[++top] = u;
    }

    // 构建虚树，返回根
    int build(vector<int>& keys) {
        sort(keys.begin(), keys.end(),
             [](int a, int b) { return dfn[a] < dfn[b]; });
        keys.erase(unique(keys.begin(), keys.end()), keys.end());

        nodes_used.clear();
        top = 0;
        int root = 1;
        if (keys.empty() || keys[0] != root) {
            stk[++top] = root;
        }
        for (int u : keys) {
            insert(u);
        }
        while (top > 1) {
            add_edge(stk[top - 1], stk[top]);
            top--;
        }
        return stk[1]; // 虚树的根
    }

    // 在虚树上做 DP：求连接所有关键点的最小边权和
    long long dp_vt[MAXN];
    bool is_key[MAXN];

    long long solve_min_cost(int root, vector<int>& keys) {
        for (int u : keys) is_key[u] = true;

        function<void(int)> dfs = [&](int u) {
            dp_vt[u] = 0;
            for (int v : vt_adj[u]) {
                dfs(v);
                long long edge_len = dist_tree(u, v);
                if (is_key[v] || dp_vt[v] > 0) {
                    dp_vt[u] += dp_vt[v] + edge_len;
                }
            }
        };
        dfs(root);

        for (int u : keys) is_key[u] = false;
        long long res = dp_vt[root];

        // 清空虚树
        for (int u : nodes_used) vt_adj[u].clear();
        return res;
    }
}

// ===================== 点分治 =====================
namespace CentroidDecomp {
    bool removed[MAXN];
    int sz[MAXN], maxp[MAXN];
    int centroid_val, min_maxp_val;

    void get_sz(int u, int f) {
        sz[u] = 1;
        for (auto [v, w] : adj[u]) {
            if (v == f || removed[v]) continue;
            get_sz(v, u);
            sz[u] += sz[v];
        }
    }

    void get_centroid(int u, int f, int tree_sz) {
        maxp[u] = 0;
        for (auto [v, w] : adj[u]) {
            if (v == f || removed[v]) continue;
            get_centroid(v, u, tree_sz);
            maxp[u] = max(maxp[u], sz[v]);
        }
        maxp[u] = max(maxp[u], tree_sz - sz[u]);
        if (maxp[u] < min_maxp_val) {
            min_maxp_val = maxp[u];
            centroid_val = u;
        }
    }

    int find_centroid(int u) {
        get_sz(u, 0);
        min_maxp_val = INT_MAX;
        get_centroid(u, 0, sz[u]);
        return centroid_val;
    }

    // 收集从 u 出发的路径
    vector<long long> cur_paths;
    void collect(int u, int f, long long d) {
        cur_paths.push_back(d);
        for (auto [v, w] : adj[u]) {
            if (v == f || removed[v]) continue;
            collect(v, u, d + w);
        }
    }

    // 统计经过重心的路径数（权值和 == target）
    long long count_target;
    long long count_paths(int c) {
        long long ans = 0;
        map<long long, int> seen;
        seen[0] = 1; // 从 c 自身出发

        for (auto [v, w] : adj[c]) {
            if (removed[v]) continue;
            cur_paths.clear();
            collect(v, c, w);

            // 查询当前子树与之前子树的配对
            for (long long d : cur_paths) {
                long long need = count_target - d;
                if (seen.count(need)) {
                    ans += seen[need];
                }
            }
            // 将当前子树的路径加入 seen
            for (long long d : cur_paths) {
                seen[d]++;
            }
        }
        return ans;
    }

    long long total_ans;

    void solve(int u) {
        int c = find_centroid(u);
        removed[c] = true;

        total_ans += count_paths(c);

        for (auto [v, w] : adj[c]) {
            if (!removed[v]) {
                solve(v);
            }
        }
    }

    long long run(long long target) {
        count_target = target;
        total_ans = 0;
        memset(removed, false, sizeof(removed));
        solve(1);
        return total_ans;
    }
}

// ===================== 主函数 =====================
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // LCA 预处理
    dfs_lca(1, 0, 0, 0);

    // 换根 DP
    Reroot::solve();
    cout << "=== Rerooting DP ===" << "\n";
    for (int i = 1; i <= n; i++) {
        cout << "ans[" << i << "] = " << Reroot::ans[i] << "\n";
    }

    // 虚树查询示例
    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        vector<int> keys(k);
        for (int i = 0; i < k; i++) cin >> keys[i];
        int vt_root = VirtualTree::build(keys);
        long long cost = VirtualTree::solve_min_cost(vt_root, keys);
        cout << cost << "\n";
    }

    // 点分治
    long long target;
    cin >> target;
    cout << CentroidDecomp::run(target) << "\n";

    return 0;
}

八、换根 DP 的进阶：不可逆操作与多状态

8.1 当合并操作不可逆时

前面提到，如果合并操作 \(\oplus\) 是加法，换根时只需减去子树贡献即可。但如果 \(\oplus\) 是取最值（\(\max\)），则没有逆运算——你不能从 \(\max(a, b)\) 和 \(b\) 还原出 \(a\)（当 \(a = b\) 时信息丢失）。

解决方案有两种：

方案一：前缀/后缀合并。如第二节所示，对每个节点的子节点列表维护前缀和后缀合并结果，查询”去掉某个子节点后的结果”时拼接前缀和后缀。空间 \(O(n)\)（因为子节点总数为 \(n - 1\)），时间 \(O(n)\)。

方案二：维护最大值和次大值。如果只需要最值，记录前两名（来自不同子树）即可。当最大值来自要去掉的子树时，用次大值代替。第二节中”树的直径端点”的例子即采用此方案。

8.2 多状态换根 DP

有时候每个节点的 DP 值不止一个维度。例如在”最大独立集”的换根版本中，需要维护 \(dp[u][0]\) 和 \(dp[u][1]\) 两个状态。换根时，需要分别对两个状态做贡献的增减。

一般来说，如果单根的 DP 状态为一个向量 \(\mathbf{dp}[u] \in \mathbb{R}^d\)，换根的转移可以表示为矩阵乘法：

\[\mathbf{dp}_{\text{full}}[v] = M_{u \to v} \cdot \mathbf{dp}_{\text{full}}[u]\]

其中 \(M_{u \to v}\) 是一个 \(d \times d\) 的转移矩阵。如果 \(d\) 是常数，每次转移 \(O(d^2)\)，总复杂度仍为 \(O(n)\)。

8.3 例题：换根最大独立集

对每个节点 \(u\)，求以 \(u\) 为根时整棵树的最大独立集权值。

这个问题的换根比较复杂，因为选/不选的状态是耦合的。一种做法是用”贡献”的观点：

// 第一次 DFS
dp[u][0] = Σ max(dp[v][0], dp[v][1])
dp[u][1] = w[u] + Σ dp[v][0]

// 换根时，从 u 推 v：
// 需要知道"去掉 v 后，u 的 dp[u][0] 和 dp[u][1]"
// dp_without_v[u][0] = dp[u][0] - max(dp[v][0], dp[v][1]) + 来自父方向的贡献
// dp_without_v[u][1] = dp[u][1] - dp[v][0] + 来自父方向的贡献

实际实现中通常用前缀后缀的方式来避免减法，以处理 \(\max\) 不可逆的情况。

九、工程实践中的注意事项

9.1 常见陷阱对照表

陷阱	描述	解决方案
栈溢出	树退化为链时递归深度达 \(n\)	Linux 下 `ulimit -s unlimited`；或改用非递归 DFS
数组清空	多组数据时 `memset` 整个数组导致 TLE	只清空 DFS 中访问过的节点（用 `vector` 记录）
虚树不清空	上次查询的边残留到下次查询	DFS 清空或记录 `nodes_used`
边权 vs 点权	混淆导致 DP 转移公式错误	统一转换：将边权归并到子节点上
整数溢出	距离和、背包值超过 `int` 范围	使用 `long long`，合并时注意中间结果
有根 vs 无根	忘记处理”无根树当有根树做”的边界	始终记录 `fa` 参数，或用 `parent[]` 数组
点分治重复计数	不同子树的路径被同一子树内的路径干扰	严格按子树顺序处理，先查询后插入
LCA 查询 \(O(1)\) vs \(O(\log n)\)	虚树中频繁查 LCA 成为瓶颈	预处理 Sparse Table 做 \(O(1)\) LCA
树上背包枚举上界	不控制上界导致复杂度退化到 \(O(nm^2)\)	严格限制 \(j\) 的范围为 \(\min(sz[u], m)\)
非递归 DFS 的子节点顺序	栈模拟时子节点顺序可能反转	如果顺序有影响，逆序压栈

9.2 非递归 DFS 模板

当节点数超过 \(10^5\) 时，递归 DFS 在某些评测环境下会爆栈。以下是非递归后序遍历的模板：

void dfs_iterative(int root) {
    // 用栈模拟 DFS，先做一遍前序确定顺序
    vector<int> order;
    vector<int> par(n + 1, 0);
    stack<int> stk;
    stk.push(root);
    while (!stk.empty()) {
        int u = stk.top(); stk.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (v == par[u]) continue;
            par[v] = u;
            stk.push(v);
        }
    }
    // 逆序处理 = 后序遍历
    reverse(order.begin(), order.end());
    for (int u : order) {
        // 在此处做自底向上的 DP
        for (int v : adj[u]) {
            if (v == par[u]) continue;
            dp[u] += dp[v] + sz[v]; // 以距离和为例
            sz[u] += sz[v];
        }
        sz[u] += 1;
    }
}

9.3 调试技巧

小样例手算：树形 DP 的 bug 最常见于转移公式的细节。先在 3-5 个节点的小树上手算，确认公式无误。
打印子树信息：在 DFS 中打印 dp[u]、sz[u] 等中间值，与手算对照。
对拍：写一个 \(O(n^2)\) 的暴力程序与 \(O(n)\) 或 \(O(n \log n)\) 的优化程序对拍。

十、经典题目选讲

10.1 CF 1187E：树上距离和（换根 DP）

题意：给定一棵 \(n\) 个节点的无权树，对每个节点 \(u\) 求 \(f(u) = \sum_{v=1}^{n} \text{dist}(u, v)\)。

这正是我们在第二节详细讨论的问题。直接应用换根 DP 的两次 DFS 即可，复杂度 \(O(n)\)。

10.2 HNOI 2014：世界树（虚树 + 换根 DP）

题意：一棵 \(n\) 个节点的树，\(q\) 次查询，每次给出 \(k\) 个关键点（议事处），每个非关键节点归属于距它最近的关键点管辖。求每个关键点管辖多少节点。

做法： 1. 对每次查询构建虚树。 2. 在虚树上做两次 DFS（换根），确定虚树上每条边的”管辖分界点”。 3. 利用原树的子树大小计算每个关键点管辖的节点数。

复杂度：\(O(n \log n + \sum k_i \log k_i)\)。

10.3 POI 2014：Rally（点分治变体）

题意：给定一棵 \(n\) 个节点的带权树和一个值 \(k\)，统计满足 \(\text{dist}(u, v) = k\) 的无序对 \((u, v)\) 的数量。

做法：点分治 + 排序 + 双指针。对每个重心，收集子树中的路径长度，排序后用双指针统计和为 \(k\) 的对数。注意减去同一子树内的贡献。

复杂度：\(O(n \log^2 n)\)。

10.4 NOI 2014：购票（点分治 + 凸包优化）

这是点分治与其他优化技巧结合的高级例题。大致思路是在点分治的框架下，对每个重心维护一个凸包，利用斜率优化来做转移。复杂度 \(O(n \log^2 n)\)。

十一、复杂度总结与横向对比

技术	适用场景	时间复杂度	空间复杂度
基础树形 DP	单次计算子树信息	\(O(n)\)	\(O(n)\)
换根 DP	所有节点为根的答案	\(O(n)\)	\(O(n)\)
虚树	多次查询，关键点少	\(O(\sum k_i \log k_i)\)	\(O(n)\)（预处理）
树上背包	有依赖的背包	\(O(nm)\)	\(O(nm)\)
点分治	树上路径统计	\(O(n \log n)\)	\(O(n)\)
点分树	在线路径查询/修改	\(O(n \log^2 n)\) 建树	\(O(n \log n)\)

几点个人观察：

换根 DP 是性价比最高的技巧。它只需要在标准树形 DP 的基础上增加一次 DFS，就能将单根扩展为全根，且不增加渐近复杂度。掌握它应该是学习树形 DP 后的第一优先级。
虚树的价值在于”聚焦”。当查询涉及的关键点远少于总节点数时，虚树将问题规模压缩到关键点级别。但它的构建依赖于 LCA 预处理，实现较为繁琐。
树上背包的复杂度分析是竞赛中最容易搞错的地方之一。很多人写出 \(O(nm)\) 的代码但认为自己写的是 \(O(nm^2)\)，或者反过来。关键在于理解”每对节点只在 LCA 处被配对一次”这个论证。
点分治的思想——找重心再分治——是一种非常通用的范式。它不仅适用于路径计数，还可以与凸包、FFT 等技巧结合，处理更复杂的问题。

十二、总结与展望

树形 DP 是一个庞大的体系。本文从最基础的子树 DP 出发，经过换根 DP、虚树、树上背包，到点分治与点分树，勾勒了这个体系的主干。每一种技巧都有其独特的适用场景和精妙之处。

几条学习建议：

先掌握基础。子树大小、最大独立集、最长路径——这些经典问题的 DP 写法必须烂熟于心。
理解换根的本质。换根不是”重新做一遍 DP”，而是”利用已有信息做增量修改”。这种增量思想在很多算法中都有体现。
虚树是工程思维的胜利。它的正确性不难理解，难的是实现时的细节处理——LCA 的 \(O(1)\) 查询、栈的维护、清空策略。
点分治需要多练。分治层数的正确性依赖于重心的性质，处理经过重心的路径时容斥的正确性需要仔细推敲。

树上的世界远不止于此。树链剖分（HLD）、Euler Tour 技巧、树哈希、LCT（Link-Cut Tree）等都是与树形 DP 紧密相关的技术。而在实际工程中，树形结构出现在编译器的 AST、文件系统的目录树、网络的路由表等众多场景中，树形 DP 的思想有着广泛的应用。

我个人认为，树形 DP 之所以优美，在于它完美地利用了树的”无环”性质——这使得子问题之间不存在循环依赖，DP 的拓扑序由树结构天然给出。相比图上的 DP（往往需要额外的拓扑排序或状态压缩），树形 DP 的结构清晰、转移自然，是动态规划中最”纯粹”的形式之一。

参考资料

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 15: Dynamic Programming.
Competitive Programmer’s Handbook, Antti Laaksonen, Chapter 14: Tree Algorithms.
刘汝佳, 陈锋. (2013). 《算法竞赛入门经典——训练指南》. 清华大学出版社.
OI Wiki: 树形 DP. https://oi-wiki.org/dp/tree/
OI Wiki: 虚树. https://oi-wiki.org/graph/virtual-tree/
OI Wiki: 点分治. https://oi-wiki.org/graph/centroid-decomposition/
Codeforces Blog: Rerooting technique. https://codeforces.com/blog/entry/44351
李煜东. (2014). 《算法竞赛进阶指南》. 河南电子音像出版社.

算法系列导航：上一篇：最近点对 | 下一篇：状压 DP

相关阅读：线段树与树状数组 | 区间 DP 与矩阵链乘