以下是 LeetCode 2646“最小化旅行的价格总和”的 C++ 实现，思路与 Java 版本一致，采用 DFS 统计节点访问次数 + 树形 DP。

C++ 代码

```cpp
class Solution {
    vector<vector<int>> graph;
    vector<int> price;
    vector<int> count;

    // 返回是否存在从 u 到 target 的路径，若存在则累加沿途节点的 count
    bool dfsCount(int u, int parent, int target) {
        if (u == target) {
            count[u]++;
            return true;
        }
        for (int v : graph[u]) {
            if (v != parent && dfsCount(v, u, target)) {
                count[u]++;
                return true;
            }
        }
        return false;
    }

    // 返回 pair: first = 当前节点不半价的最小总价, second = 当前节点半价的最小总价
    pair<int, int> dfs(int u, int parent) {
        int notHalf = price[u] * count[u];      // 当前节点不半价
        int half = price[u] * count[u] / 2;     // 当前节点半价

        for (int v : graph[u]) {
            if (v == parent) continue;
            auto [childNotHalf, childHalf] = dfs(v, u);
            notHalf += min(childNotHalf, childHalf); // 父不半价，子可选最优
            half += childNotHalf;                     // 父半价，子必须不半价
        }
        return {notHalf, half};
    }

public:
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        this->price = price;
        graph.resize(n);
        for (auto& e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        count.assign(n, 0);
        for (auto& trip : trips) {
            dfsCount(trip[0], -1, trip[1]);
        }

        auto [rootNotHalf, rootHalf] = dfs(0, -1);
        return min(rootNotHalf, rootHalf);
    }
};
```

代码说明

1. 统计访问次数
      dfsCount 函数递归查找从 start 到 end 的路径，并将路径上所有节点的 count 加 1。
2. 树形 DP
      dfs 函数返回 pair<int,int>：
   · first：当前节点 不半价 时，子树的最小总代价
   · second：当前节点 半价 时，子树的最小总代价
3. 状态转移
   · 当前节点不半价 → 子节点可以半价或不半价，取 min
   · 当前节点半价 → 子节点 必须不半价
4. 最终答案
      对根节点取 min(不半价, 半价)

复杂度分析

· 时间：O(n * m)，n 为节点数，m 为路径数（最坏情况每条路径遍历整棵树）
· 空间：O(n)，递归栈 + 邻接表

优化提示

如果数据规模较大（例如 n, m <= 10^5），可以使用 LCA + 差分数组 优化路径统计，将单次路径复杂度降为 O(log n)。需要我提供这个优化版本吗？