树形DP进阶：结合dfn序的线性化树问题求解技巧

- 一、dfn序与树的线性化
- - 1.1 dfn序的基本概念
  - 1.2 树形DP结合dfn序的优势
- 二、核心应用：子树区间的DP优化
- - 2.1 子树权值和的快速查询与更新
  - - 问题描述
    - 结合dfn序的解法
    - 代码实现（前缀和版本）
    - 优化说明
  - 2.2 树形DP与线性DP的结合（子树序列拼接）
  - - 问题描述
    - 结合dfn序的解法
    - 代码实现
    - 核心思路
- 三、进阶技巧：dfn序与树形DP的状态融合
- - 3.1 带限制的子树节点选择（结合线段树）
  - - 问题描述
    - 解法思路
    - 关键代码
  - 3.2 dfn序在多子树合并中的应用
- 四、dfn序的优化边界
- - 4.1 适用场景
  - 4.2 局限性
  - 总结

树形DP求解中，我们常遇到需要频繁处理“子树区间查询”“多子树合并”或“树与线性结构交互”的问题，这类问题单纯依靠递归遍历往往难以高效实现，而dfn序（深度优先搜索序号） 作为将树结构转化为线性结构的桥梁，能显著降低问题复杂度。

一、dfn序与树的线性化

1.1 dfn序的基本概念

dfn序（Depth-First Numbering）是对树进行深度优先搜索（DFS）时，记录节点首次被访问的时间戳。它将树的层级结构转化为线性数组，同时具有一个关键特性：任意子树在dfn序中对应一个连续的区间。

具体来说，对节点u进行DFS时，记录：
- dfn[u]：节点u的入栈时间（首次访问序号）；
- size[u]：以u为根的子树包含的节点数；
- 则u的子树在dfn序中对应区间为[dfn[u], dfn[u] + size[u] - 1]。

二叉树示例：

    1/ \2   3/ \4   5

DFS访问顺序为1→2→2（回退）→3→4→4（回退）→5→5（回退）→3（回退）→1（回退），dfn序为：

dfn[1]=1，size[1]=5 → 子树区间[1,5]
dfn[2]=2，size[2]=1 → 子树区间[2,2]
dfn[3]=3，size[3]=3 → 子树区间[3,5]
dfn[4]=4，size[4]=1 → 子树区间[4,4]
dfn[5]=5，size[5]=1 → 子树区间[5,5]

1.2 树形DP结合dfn序的优势

传统树形DP通过递归处理子树，在以下场景中存在局限：

需要多次查询子树信息（如“统计子树中某属性的和”）；
需合并多个子树的线性结构（如“将子树的序列拼接后进行DP”）；
需结合线段树、前缀和等线性数据结构优化查询。

而dfn序的线性化特性可解决这些问题：

子树区间化：将子树转化为连续区间，使子树查询等价于区间查询；
线性结构复用：可直接使用前缀和、线段树等处理线性数据的工具；
状态转移简化：多子树的合并可转化为区间拼接，降低递归嵌套复杂度。

二、核心应用：子树区间的DP优化

2.1 子树权值和的快速查询与更新

问题描述

给定一棵带权树，支持两种操作：

更新某节点的权值；
查询以u为根的子树的权值和。

要求高效实现这两种操作（传统递归查询每次需O(size[u])，效率低）。

结合dfn序的解法

线性化映射：
- 对树进行DFS，计算每个节点的dfn[u]和size[u]，子树u对应区间[L, R] = [dfn[u], dfn[u] + size[u] - 1]；
- 将节点权值按dfn序存入数组val[dfn[u]] = w[u]。
前缀和/线段树优化：
- 用前缀和数组pre维护val的区间和，pre[i] = val[1] + ... + val[i]；
- 子树和查询：sum(u) = pre[R] - pre[L-1]；
- 单点更新：修改val[dfn[u]]后同步更新前缀和（或用线段树实现O(log n)更新）。

代码实现（前缀和版本）

import java.util.*;public class SubtreeSumWithDFN {List<List<Integer>> adj;int[] w; // 节点权值int[] dfn, size; // dfn序和子树大小long[] pre; // 前缀和数组int n, dfnCnt;public SubtreeSumWithDFN(int n, int[] w) {this.n = n;this.w = w;adj = new ArrayList<>();for (int i = 0; i < n; i++) {adj.add(new ArrayList<>());}dfn = new int[n];size = new int[n];dfnCnt = 0;}public void addEdge(int u, int v) {adj.get(u).add(v);adj.get(v).add(u);}// 计算dfn序和size（根节点设为0）private void dfs(int u, int parent) {dfn[u] = dfnCnt++;size[u] = 1;for (int v : adj.get(u)) {if (v == parent) continue;dfs(v, u);size[u] += size[v];}}// 初始化前缀和public void build() {dfs(0, -1);pre = new long[n + 1]; // pre[0] = 0, pre[1] = val[0], ...for (int u = 0; u < n; u++) {pre[dfn[u] + 1] = pre[dfn[u]] + w[u]; // dfn从0开始，前缀和从1开始}}// 查询子树u的权值和public long querySubtreeSum(int u) {int L = dfn[u];int R = dfn[u] + size[u] - 1;return pre[R + 1] - pre[L];}// 更新节点u的权值（delta为变化量）public void update(int u, int delta) {w[u] += delta;int pos = dfn[u];for (int i = pos + 1; i <= n; i++) { // 前缀和更新（低效，实际用线段树）pre[i] += delta;}}public static void main(String[] args) {int n = 5;int[] w = {10, 20, 30, 40, 50}; // 节点0~4的权值SubtreeSumWithDFN tree = new SubtreeSumWithDFN(n, w);tree.addEdge(0, 1); // 节点0对应示例中的1tree.addEdge(0, 2);tree.addEdge(2, 3);tree.addEdge(2, 4);tree.build();System.out.println(tree.querySubtreeSum(2)); // 子树2包含节点2,3,4 → 30+40+50=120tree.update(3, 10); // 节点3权值+10 → 50System.out.println(tree.querySubtreeSum(2)); // 30+50+50=130}
}

优化说明

上述代码的更新操作是O(n)，实际应用中应改用线段树或树状数组，将更新和查询复杂度均降至O(log n)。
核心思想是利用dfn序的区间特性，将“子树查询”转化为“区间查询”，彻底摆脱递归遍历的低效。

2.2 树形DP与线性DP的结合（子树序列拼接）

问题描述

给定一棵二叉树，每个节点有一个字符，求所有子树对应的字符串中，最长回文子序列的长度。

示例：节点3的子树包含字符'a'、'b'、'a'，对应字符串"aba"，最长回文子序列长度为3。

结合dfn序的解法

子树字符串的线性化：
- 对树进行DFS，按dfn序记录节点字符，得到数组chars，子树u的字符串对应chars[L..R]（L=dfn[u], R=dfn[u]+size[u]-1）。
区间DP预处理：
- 预处理线性数组chars的区间回文子序列长度lps[L][R]（经典区间DP，lps[L][R]表示chars[L..R]的最长回文子序列长度）。
树形DP映射：
- 对每个节点u，其最长回文子序列长度即为lps[L][R]，直接通过dfn区间查询获取。

代码实现

import java.util.*;public class SubtreePalindromeWithDFN {List<List<Integer>> adj;char[] chars; // 节点字符int[] dfn, size;int[][] lps; // 区间最长回文子序列int n, dfnCnt;public SubtreePalindromeWithDFN(int n, char[] chars) {this.n = n;this.chars = chars;adj = new ArrayList<>();for (int i = 0; i < n; i++) {adj.add(new ArrayList<>());}dfn = new int[n];size = new int[n];dfnCnt = 0;lps = new int[n][n];}public void addEdge(int u, int v) {adj.get(u).add(v);}// 计算dfn序和size（二叉树，左子树优先）private void dfs(int u) {dfn[u] = dfnCnt++;size[u] = 1;for (int v : adj.get(u)) { // 假设子节点按左右顺序存储dfs(v);size[u] += size[v];}}// 预处理区间最长回文子序列private void preprocessLPS() {// 区间DP：lps[L][R] = 最长回文子序列长度for (int i = n - 1; i >= 0; i--) {lps[i][i] = 1; // 单个字符for (int j = i + 1; j < n; j++) {if (chars[i] == chars[j]) {lps[i][j] = (j == i + 1) ? 2 : lps[i + 1][j - 1] + 2;} else {lps[i][j] = Math.max(lps[i + 1][j], lps[i][j - 1]);}}}}// 获取子树u的最长回文子序列长度public int getMaxPalindrome(int u) {int L = dfn[u];int R = dfn[u] + size[u] - 1;return lps[L][R];}public static void main(String[] args) {int n = 3;char[] chars = {'a', 'b', 'a'}; // 节点0: 'a', 节点1: 'b', 节点2: 'a'SubtreePalindromeWithDFN tree = new SubtreePalindromeWithDFN(n, chars);tree.addEdge(0, 1); // 0是根，1和2是子节点（模拟二叉树0->1->2）tree.addEdge(1, 2);tree.dfs(0);tree.preprocessLPS();System.out.println(tree.getMaxPalindrome(0)); // 子树0: "aba" → 3System.out.println(tree.getMaxPalindrome(1)); // 子树1: "ba" → 1}
}

核心思路

通过dfn序将“子树字符串”转化为“线性区间”，复用区间DP的结果，避免对每个子树单独计算回文序列（传统方法复杂度O(n^3)，优化后为O(n^2)）。
体现了“树的线性化”与“线性DP预处理”结合的高效性，尤其适合子树操作频繁的场景。

三、进阶技巧：dfn序与树形DP的状态融合

3.1 带限制的子树节点选择（结合线段树）

问题描述

给定一棵树上每个节点有价值v[u]和颜色c[u]，求一个子树u，使得：

子树中所有节点的颜色均为k；
子树的总价值最大。

解法思路

dfn序与颜色过滤：
- 按dfn序遍历树，记录每个颜色k对应的节点在dfn数组中的位置，形成colorPos[k] = [p1, p2, ...]（升序排列）。
区间最大值查询：
- 用线段树维护dfn序的价值前缀和，对颜色k，在colorPos[k]中查找连续区间（对应子树），计算其价值和并取最大值。
子树验证：
- 对颜色k的每个连续区间[L, R]，检查是否存在节点u使得dfn[u] = L且dfn[u] + size[u] - 1 = R（即该区间是合法子树）。

关键代码

// 检查区间[L, R]是否为合法子树
private boolean isSubtree(int L, int R) {int u = findNodeByDFN(L); // 根据dfn值找到节点u（需维护dfn到节点的映射）return (dfn[u] + size[u] - 1) == R;
}// 查找颜色k的最大子树价值
public int maxSubtreeValue(int k) {List<Integer> positions = colorPos.get(k);int maxSum = 0;// 遍历颜色k的所有节点位置，检查连续区间是否为子树for (int i = 0; i < positions.size(); i++) {int L = positions.get(i);for (int j = i; j < positions.size(); j++) {int R = positions.get(j);if (!isSubtree(L, R)) continue;int sum = segmentTree.query(L, R); // 线段树查询区间和maxSum = Math.max(maxSum, sum);}}return maxSum;
}