题目链接：2646. 最小化旅行的价格总和
方法一：dfs + 树形dp
解题思路
- 先不考虑哪些节点的代价需要减半：
- 由题可知，本题的数据结构是一个图存储的无根树，那么表示从 \(start\) 到 \(end\) 之间只有唯一的一条路线，那么我们对于 \(trips\) 中的每个询问，通过 \(dfs\) 找寻从 \(st\) 到 \(ed\) 过程中走过的节点，最终计算出每个节点需要经过的次数，然后乘以对应的 \(price\) 得到当前节点所需要的总代价。
- 接下来考虑将哪些非相邻节点的价格减半：
- 为了使得最终代价最小，那么应该选择其中所占代价最大的方案，并将其对应的节点价格减半；
- 那么问题就变成了选择非相邻节点构成的集合的最大代价；
- 即典型的树形 \(dp\) 问题：
- 当前节点由两种选择，\(select\)，\(no\)_\(select\)，当前节点的值可以由其所有非自身的邻接点转移过来；
select = val + sum(next.second)，当前节点选择后，邻接点不能选择；no_select = sum(max(next.first, next.second))，当前节点不选择，邻接点可选可不选，取其中最大值；- 返回 \(\{select, no_select\}\)；
- 递归边界：由于每次都是找的邻接点，当都遍历完时，递归会自动结束。
代码
class Solution {
public:
int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
vector<vector<int>> adj(n);
vector<int> w(n), path;
for (auto &e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
function<void(int, int, int)> dfs1 = [&](int u, int fa, int ed) -> void {
if (u == ed) {
for (auto &v : path) w[v] ++ ;
w[u] ++ ;
return ;
}
path.push_back(u);
for (auto &v : adj[u])
if (v != fa) dfs1(v, u, ed);
path.pop_back();
};
for (int i = 0; i < trips.size(); i ++ ) {
int st = trips[i][0], ed = trips[i][1];
dfs1(st, -1, ed);
}
int sum = 0;
for (int i = 0; i < n; i ++ ) {
w[i] = w[i] * price[i];
sum += w[i];
}
function<pair<int, int>(int, int)> dfs2 = [&](int u, int fa) -> pair<int, int> {
int select = w[u], not_select = 0;
pair<int, int> next;
for (auto &v : adj[u])
if (v != fa) {
next = dfs2(v, u);
select += next.second;
not_select += max(next.first, next.second);
}
return {select, not_select};
};
pair<int, int> ans = dfs2(0, -1);
return sum - max(ans.first, ans.second) / 2;
}
};
复杂度分析
时间复杂度：对于 \(trips\) 的处理为 \(O(nm)\)，\(m = trips.size()\)；树形 \(dp\) 为 \(O(n)\)；
空间复杂度：\(O(n)\)。
方法二：树上差分 + LCA
待续...