树上DP与状压DP

树上动态规划和状态压缩动态规划是竞赛编程中的高级技巧。树上DP利用树的递归结构进行状态转移，状压DP通过二进制位表示状态集合，都能解决复杂的组合优化问题。

树上DP基础

树上DP的核心思想是在树的后序遍历过程中，利用子树的信息计算当前节点的状态。

树的直径 - 经典树上DP

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class TreeDiameter {
private:
    vector<vector<pair<int, int>>> adj;
    int maxDiameter = 0;
    
public:
    TreeDiameter(int n) : adj(n) {}
    
    void addEdge(int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    // 返回以node为根的子树中，从node出发的最长路径
    int dfs(int node, int parent) {
        int maxPath1 = 0, maxPath2 = 0;
        
        for (auto& edge : adj[node]) {
            int child = edge.first;
            int weight = edge.second;
            
            if (child == parent) continue;
            
            int childPath = dfs(child, node) + weight;
            
            // 维护最长和次长路径
            if (childPath > maxPath1) {
                maxPath2 = maxPath1;
                maxPath1 = childPath;
            } else if (childPath > maxPath2) {
                maxPath2 = childPath;
            }
        }
        
        // 更新直径（经过当前节点的最长路径）
        maxDiameter = max(maxDiameter, maxPath1 + maxPath2);
        
        return maxPath1;
    }
    
    int getDiameter() {
        maxDiameter = 0;
        dfs(0, -1);
        return maxDiameter;
    }
};

// 树的重心
class TreeCentroid {
private:
    vector<vector<int>> adj;
    vector<int> subtreeSize;
    int n, centroid, minMaxSubtree;
    
public:
    TreeCentroid(int n) : n(n), adj(n), subtreeSize(n) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    int dfs(int node, int parent) {
        subtreeSize[node] = 1;
        int maxSubtree = 0;
        
        for (int child : adj[node]) {
            if (child == parent) continue;
            
            int childSubtreeSize = dfs(child, node);
            subtreeSize[node] += childSubtreeSize;
            maxSubtree = max(maxSubtree, childSubtreeSize);
        }
        
        // 考虑删除当前节点后，上方的子树大小
        maxSubtree = max(maxSubtree, n - subtreeSize[node]);
        
        if (maxSubtree < minMaxSubtree) {
            minMaxSubtree = maxSubtree;
            centroid = node;
        }
        
        return subtreeSize[node];
    }
    
    int findCentroid() {
        minMaxSubtree = n;
        dfs(0, -1);
        return centroid;
    }
};

int main() {
    // 测试树的直径
    TreeDiameter td(6);
    td.addEdge(0, 1, 2);
    td.addEdge(0, 2, 3);
    td.addEdge(1, 3, 1);
    td.addEdge(1, 4, 4);
    td.addEdge(2, 5, 2);
    
    cout << "树的直径: " << td.getDiameter() << endl;
    
    // 测试树的重心
    TreeCentroid tc(6);
    tc.addEdge(0, 1);
    tc.addEdge(0, 2);
    tc.addEdge(1, 3);
    tc.addEdge(1, 4);
    tc.addEdge(2, 5);
    
    cout << "树的重心: " << tc.findCentroid() << endl;
    
    return 0;
}

树的直径通过树上DP在每个节点维护最长和次长路径。树的重心是删除后剩余连通分量最大值最小的节点。

换根DP技巧

换根DP先以任意节点为根计算答案，然后通过状态转移计算其他节点为根的答案。

换根DP - 计算每个节点到其他所有节点的距离和

#include <iostream>
#include <vector>
using namespace std;

class RerootingDP {
private:
    vector<vector<int>> adj;
    vector<long long> subtreeSum;    // 子树内距离和
    vector<int> subtreeSize;         // 子树大小
    vector<long long> ans;           // 每个节点的答案
    int n;
    
public:
    RerootingDP(int n) : n(n), adj(n), subtreeSum(n), subtreeSize(n), ans(n) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 第一次DFS：计算以node为根时的子树信息
    void dfs1(int node, int parent) {
        subtreeSize[node] = 1;
        subtreeSum[node] = 0;
        
        for (int child : adj[node]) {
            if (child == parent) continue;
            
            dfs1(child, node);
            subtreeSize[node] += subtreeSize[child];
            subtreeSum[node] += subtreeSum[child] + subtreeSize[child];
        }
    }
    
    // 第二次DFS：换根计算每个节点的答案
    void dfs2(int node, int parent) {
        for (int child : adj[node]) {
            if (child == parent) continue;
            
            // 计算child为根时的答案
            // 从node转移到child：
            // 1. child的子树贡献不变
            // 2. 其余部分（包括node）的贡献需要重新计算
            
            long long childSubtreeSum = subtreeSum[child];
            int childSubtreeSize = subtreeSize[child];
            
            // 从node中移除child的贡献
            subtreeSum[node] -= (childSubtreeSum + childSubtreeSize);
            subtreeSize[node] -= childSubtreeSize;
            
            // 将node的贡献加到child
            subtreeSum[child] += (subtreeSum[node] + subtreeSize[node]);
            subtreeSize[child] += subtreeSize[node];
            
            ans[child] = subtreeSum[child];
            
            dfs2(child, node);
            
            // 恢复原始值
            subtreeSum[child] = childSubtreeSum;
            subtreeSize[child] = childSubtreeSize;
            subtreeSum[node] += (childSubtreeSum + childSubtreeSize);
            subtreeSize[node] += childSubtreeSize;
        }
    }
    
    vector<long long> solve() {
        dfs1(0, -1);
        ans[0] = subtreeSum[0];
        dfs2(0, -1);
        return ans;
    }
};

int main() {
    RerootingDP rd(6);
    rd.addEdge(0, 1);
    rd.addEdge(0, 2);
    rd.addEdge(1, 3);
    rd.addEdge(1, 4);
    rd.addEdge(2, 5);
    
    vector<long long> result = rd.solve();
    
    cout << "每个节点到其他节点的距离和:" << endl;
    for (int i = 0; i < result.size(); i++) {
        cout << "节点 " << i << ": " << result[i] << endl;
    }
    
    return 0;
}

换根DP通过两次DFS避免为每个根重新计算。它通过考虑移动根时贡献如何变化来高效转移状态。

状压DP基础

状态压缩动态规划使用二进制位表示状态集合，适用于指数状态空间但参数范围较小的问题。

旅行商问题 - 状压DP经典应用

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class TSP {
private:
    vector<vector<int>> dist;
    vector<vector<int>> dp;
    int n;
    
public:
    TSP(vector<vector<int>>& distances) : dist(distances) {
        n = dist.size();
        dp.assign(1 << n, vector<int>(n, INT_MAX));
    }
    
    int solve() {
        // 基础情况：从城市0开始
        dp[1][0] = 0; // mask = 1 (只访问了城市0), 当前城市 = 0
        
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int u = 0; u < n; u++) {
                if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX) continue;
                
                for (int v = 0; v < n; v++) {
                    if (mask & (1 << v)) continue; // 城市v已经访问过
                    
                    int newMask = mask | (1 << v);
                    dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
                }
            }
        }
        
        // 找到回到起始城市的最小代价
        int result = INT_MAX;
        int finalMask = (1 << n) - 1; // 所有城市都访问过
        
        for (int u = 1; u < n; u++) {
            if (dp[finalMask][u] != INT_MAX) {
                result = min(result, dp[finalMask][u] + dist[u][0]);
            }
        }
        
        return result == INT_MAX ? -1 : result;
    }
    
    vector<int> getPath() {
        vector<int> path;
        int mask = (1 << n) - 1;
        int current = 0;
        
        // 找到给出最小代价的结束城市
        for (int u = 1; u < n; u++) {
            if (dp[mask][u] + dist[u][0] < dp[mask][current] + dist[current][0]) {
                current = u;
            }
        }
        
        // 重构路径
        while (mask != 1) {
            path.push_back(current);
            int prevMask = mask ^ (1 << current);
            
            for (int u = 0; u < n; u++) {
                if ((prevMask & (1 << u)) && 
                    dp[prevMask][u] + dist[u][current] == dp[mask][current]) {
                    mask = prevMask;
                    current = u;
                    break;
                }
            }
        }
        
        path.push_back(0);
        reverse(path.begin(), path.end());
        return path;
    }
};

// 使用状压DP的任务分配问题
class AssignmentProblem {
private:
    vector<vector<int>> cost;
    vector<int> dp;
    int n;
    
public:
    AssignmentProblem(vector<vector<int>>& costs) : cost(costs) {
        n = cost.size();
        dp.assign(1 << n, INT_MAX);
    }
    
    int solve() {
        dp[0] = 0; // 没有任务被分配
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == INT_MAX) continue;
            
            int person = __builtin_popcount(mask); // 已分配任务的数量
            if (person >= n) continue;
            
            for (int task = 0; task < n; task++) {
                if (mask & (1 << task)) continue; // 任务已被分配
                
                int newMask = mask | (1 << task);
                dp[newMask] = min(dp[newMask], dp[mask] + cost[person][task]);
            }
        }
        
        return dp[(1 << n) - 1];
    }
};

int main() {
    // 测试TSP
    vector<vector<int>> distances = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    
    TSP tsp(distances);
    int minCost = tsp.solve();
    vector<int> path = tsp.getPath();
    
    cout << "TSP最小代价: " << minCost << endl;
    cout << "最优路径: ";
    for (int i = 0; i < path.size(); i++) {
        cout << path[i];
        if (i < path.size() - 1) cout << " -> ";
    }
    cout << " -> 0" << endl;
    
    // 测试任务分配问题
    vector<vector<int>> costs = {
        {9, 2, 7, 8},
        {6, 4, 3, 7},
        {5, 8, 1, 8},
        {7, 6, 9, 4}
    };
    
    AssignmentProblem ap(costs);
    cout << "\n任务分配最小代价: " << ap.solve() << endl;
    
    return 0;
}

状压DP使用二进制位编码访问状态。TSP使用dp[mask][u]表示访问mask中城市并以u结尾的最小代价。任务分配问题将任务最优分配给人员。

高级树上DP应用

高级树上DP处理复杂约束和多状态维度，常与其他技巧结合使用。

树着色问题

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class TreeColoring {
private:
    vector<vector<int>> adj;
    vector<vector<long long>> dp;
    int n, k;
    const int MOD = 1000000007;
    
public:
    TreeColoring(int n, int k) : n(n), k(k), adj(n), dp(n, vector<long long>(k, 0)) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // dp[u][c] = 以u为根的子树中u着色为c的方案数
    void dfs(int u, int parent) {
        // 基础情况：叶子节点可以着任意颜色
        for (int c = 0; c < k; c++) {
            dp[u][c] = 1;
        }
        
        for (int v : adj[u]) {
            if (v == parent) continue;
            
            dfs(v, u);
            
            // 合并子节点v的结果
            vector<long long> newDp(k, 0);
            
            for (int uc = 0; uc < k; uc++) {
                for (int vc = 0; vc < k; vc++) {
                    if (uc != vc) { // 相邻节点必须颜色不同
                        newDp[uc] = (newDp[uc] + dp[u][uc] * dp[v][vc]) % MOD;
                    }
                }
            }
            
            dp[u] = newDp;
        }
    }
    
    long long solve() {
        dfs(0, -1);
        long long result = 0;
        for (int c = 0; c < k; c++) {
            result = (result + dp[0][c]) % MOD;
        }
        return result;
    }
};

// 树上最大权独立集
class MaxWeightIndependentSet {
private:
    vector<vector<int>> adj;
    vector<int> weight;
    vector<vector<long long>> dp;
    int n;
    
public:
    MaxWeightIndependentSet(vector<int>& weights) : weight(weights) {
        n = weight.size();
        adj.resize(n);
        dp.assign(n, vector<long long>(2, 0));
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // dp[u][0] = 不选择u时的最大权重
    // dp[u][1] = 选择u时的最大权重
    void dfs(int u, int parent) {
        dp[u][0] = 0;
        dp[u][1] = weight[u];
        
        for (int v : adj[u]) {
            if (v == parent) continue;
            
            dfs(v, u);
            
            // 如果不选择u，v可以选择或不选择
            dp[u][0] += max(dp[v][0], dp[v][1]);
            
            // 如果选择u，v不能被选择
            dp[u][1] += dp[v][0];
        }
    }
    
    long long solve() {
        dfs(0, -1);
        return max(dp[0][0], dp[0][1]);
    }
    
    vector<int> getSelectedNodes() {
        vector<int> selected;
        function<void(int, int, bool)> reconstruct = [&](int u, int parent, bool canSelect) {
            if (canSelect && dp[u][1] >= dp[u][0]) {
                selected.push_back(u);
                for (int v : adj[u]) {
                    if (v != parent) {
                        reconstruct(v, u, false);
                    }
                }
            } else {
                for (int v : adj[u]) {
                    if (v != parent) {
                        reconstruct(v, u, true);
                    }
                }
            }
        };
        
        reconstruct(0, -1, true);
        return selected;
    }
};

int main() {
    // 测试树着色
    TreeColoring tc(5, 3);
    tc.addEdge(0, 1);
    tc.addEdge(0, 2);
    tc.addEdge(1, 3);
    tc.addEdge(1, 4);
    
    cout << "用3种颜色给树着色的方案数: " << tc.solve() << endl;
    
    // 测试最大权独立集
    vector<int> weights = {10, 5, 2, 7, 8};
    MaxWeightIndependentSet mwis(weights);
    mwis.addEdge(0, 1);
    mwis.addEdge(0, 2);
    mwis.addEdge(1, 3);
    mwis.addEdge(1, 4);
    
    cout << "最大权独立集: " << mwis.solve() << endl;
    
    vector<int> selected = mwis.getSelectedNodes();
    cout << "选择的节点: ";
    for (int node : selected) {
        cout << node << " ";
    }
    cout << endl;
    
    return 0;
}

高级树上DP同时处理多个约束。树着色确保相邻节点颜色不同。最大权独立集选择不相邻节点使总权重最大。

竞赛编程技巧

树上DP核心概念：

利用树的递归结构进行自底向上的状态计算
基于子树属性和节点特征定义状态
在后序遍历过程中合并子状态计算父状态
对于需要所有节点作为潜在根的问题考虑换根

状压DP应用：

指数状态空间但参数约束较小的问题 (n ≤ 20)
子集枚举和选择问题
使用二进制表示进行状态压缩
使用位运算进行高效转移

实现技巧：

树上DP：在DFS过程中正确处理父子关系
状压DP：使用__builtin_popcount()进行位计数
内存优化：可能时使用滚动数组
状态重构：跟踪转移选择以恢复解

常见模式：

树的直径、重心和距离问题
TSP、任务分配和子集选择问题
树着色和独立集问题
具有树或子集约束的计数问题