树形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序的线性化特性可解决这些问题：

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

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

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

问题描述

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

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

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

结合dfn序的解法

1. 线性化映射：

   • 对树进行DFS，计算每个节点的dfn[u]和size[u]，子树u对应区间[L, R] = [dfn[u], dfn[u] + size[u] - 1]；
   • 将节点权值按dfn序存入数组val[dfn[u]] = w[u]。

2. 前缀和/线段树优化：

   • 用前缀和数组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序的解法

1. 子树字符串的线性化：

   • 对树进行DFS，按dfn序记录节点字符，得到数组chars，子树u的字符串对应chars[L..R]（L=dfn[u], R=dfn[u]+size[u]-1）。

2. 区间DP预处理：

   • 预处理线性数组chars的区间回文子序列长度lps[L][R]（经典区间DP，lps[L][R]表示chars[L..R]的最长回文子序列长度）。

3. 树形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；
• 子树的总价值最大。

解法思路

1. dfn序与颜色过滤：

   • 按dfn序遍历树，记录每个颜色k对应的节点在dfn数组中的位置，形成colorPos[k] = [p1, p2, ...]（升序排列）。

2. 区间最大值查询：

   • 用线段树维护dfn序的价值前缀和，对颜色k，在colorPos[k]中查找连续区间（对应子树），计算其价值和并取最大值。

3. 子树验证：

   • 对颜色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;
}

3.2 dfn序在多子树合并中的应用

当需要合并多个子树的DP状态时（如“选择k个不相交子树，使总价值最大”），dfn序的线性特性可将问题转化为“在数组中选择k个不重叠区间，使区间和最大”，直接复用线性DP的解法：

• 定义dp[i][j]表示“前i个dfn位置，选择j个子树的最大价值”；
• 转移时判断当前位置是否为子树起点，若是则可选择包含该子树（dp[i+size[u]-1][j+1] = max(dp[i+size[u]-1][j+1], dp[i-1][j] + sum(u))）。

四、dfn序的优化边界

4.1 适用场景

• 子树区间查询频繁：如子树和、子树最值、子树序列属性（回文、递增等）；
• 树与线性结构交互：需结合前缀和、线段树、滑动窗口等线性算法；
• 多子树合并问题：子树的选择、组合需满足线性约束（如不重叠、连续等）。

4.2 局限性

• 动态树不适用：树结构频繁修改（如节点插入/删除）会导致dfn序失效，需用动态树数据结构（如Link-Cut Tree）；
• 非DFS友好的问题：依赖广度优先遍历（BFS）特性的问题（如层次相关），dfn序优势不明显；
• 区间映射 overhead：对简单子树问题（如单次查询），递归遍历可能比dfn序预处理更高效。

总结

dfn序作为树结构线性化的核心工具，为树形DP提供了“降维打击”的思路——将复杂的树状问题转化为直观的线性问题，从而复用成熟的线性数据结构与算法：

1. 子树区间化：通过dfn[u]和size[u]将子树映射为连续区间，简化查询；
2. 线性工具复用：前缀和、线段树等可直接应用于子树问题，提升效率；
3. 状态融合：使树形DP与线性DP的状态转移无缝衔接，解决多子树合并等复杂场景。

掌握dfn序技巧的关键：

• 熟练计算和应用dfn与size数组；
• 敏感识别“子树问题可转化为区间问题”的场景；
• 结合具体问题选择合适的线性数据结构（前缀和、线段树等）。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～