树形动态规划实战：如何最小化旅行成本？力扣2646题深度解析

一、理解题目

题目描述了一棵树，每个节点有价格，我们需要在旅行前选择一些非相邻节点将价格减半，使得所有旅行的总价格最小。这是一个典型的树形动态规划问题。

二、解题思路

1. ‌构建树结构‌：首先将边信息转换为邻接表表示的树

2. ‌统计节点访问次数‌：通过BFS/DFS计算每个节点在所有旅行路径中被访问的次数

3. ‌动态规划求解‌：使用树形DP决定哪些节点应该减半

三、关键代码解析

1. ‌邻接表构建‌：

vector<vector<int>> tree(n);
for (const auto& edge : edges) {
    tree[edge[0]].push_back(edge[1]);
    tree[edge[1]].push_back(edge[0]);
}

这部分代码将输入的边信息转换为邻接表，方便后续遍历。

2. ‌节点访问统计‌：

vector<int> parent(n, -1);
queue<int> q;
q.push(start);
parent[start] = start;

while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (u == end) break;
    for (int v : tree[u]) {
        if (parent[v] == -1) {
            parent[v] = u;
            q.push(v);
        }
    }
}

使用BFS找到从起点到终点的路径，并记录父节点以便回溯。

3. ‌动态规划部分‌：

function<int(int, int, bool)> dfs = [&](int u, int parent, bool canHalve) {
    // ...
    int notHalve = price[u] * count[u];
    int halve = (price[u] / 2) * count[u];
    // ...
};

定义递归函数，计算当前节点减半或不减半时的最小总价格。

四、完整代码

class Solution {
public:
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        // 构建邻接表表示的树
        vector<vector<int>> tree(n);
        for (const auto& edge : edges) {
            tree[edge[0]].push_back(edge[1]);
            tree[edge[1]].push_back(edge[0]);
        }
        
        // 统计每个节点被访问的次数
        vector<int> count(n, 0);
        for (const auto& trip : trips) {
            int start = trip[0], end = trip[1];
            // 使用DFS或BFS找到路径并统计节点访问次数
            vector<int> parent(n, -1);
            queue<int> q;
            q.push(start);
            parent[start] = start;
            
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                if (u == end) break;
                for (int v : tree[u]) {
                    if (parent[v] == -1) {
                        parent[v] = u;
                        q.push(v);
                    }
                }
            }
            
            // 回溯路径并统计节点访问次数
            int node = end;
            while (node != start) {
                count[node]++;
                node = parent[node];
            }
            count[start]++;
        }
        
        // 动态规划求解最优减半策略
        // DP[u][0]表示u不减半，dp[u][1]表示u减半
        vector<vector<int>> dp(n, vector<int>(2, -1));
        
        function<int(int, int, bool)> dfs = [&](int u, int parent, bool canHalve) {
            if (dp[u][canHalve] != -1) return dp[u][canHalve];
            
            int notHalve = price[u] * count[u];
            int halve = (price[u] / 2) * count[u];
            
            for (int v : tree[u]) {
                if (v == parent) continue;
                notHalve += dfs(v, u, true);
                if (canHalve) {
                    halve += dfs(v, u, false);
                }
            }
            
            if (!canHalve) {
                dp[u][0] = notHalve;
                return notHalve;
            } else {
                dp[u][1] = min(notHalve, halve);
                return dp[u][1];
            }
        };
        
        return dfs(0, -1, true);
    }
};

五、总结

这道题结合了树遍历和动态规划两个重要算法思想，是练习树形DP的经典题目。理解状态转移方程和树遍历方法是解决此类问题的关键。