樹形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;
}