题解 | #星球游戏#

所有边的两倍减去无重复最长路径就是答案。因为题目说了任意两点之间只有一条路径，所以在我们沿着最长边走的时候，所有的分支都需要走两遍，而最长路径只需要走一遍。

class Solution {
public:
/**
* 最短距离
* @param n int整型
* @param Edge Point类vector
* @param val int整型vector
* @return long长整型
*/
vector<vector<pair<int, int>>> point_to;
int max_l = 0;
int dfs(int cur, int prev) {
int max_cur_l = 0;
for (auto next : point_to[cur]) {
if (next.first == prev) continue;
int temp = dfs(next.first, cur);
max_l = max(max_l, max_cur_l + next.second + temp);
max_cur_l = max(max_cur_l, next.second + temp);
}
return max_cur_l;
}
long long solve(int n, vector<point>& Edge, vector<int>& val) {
// write code here
point_to.resize(n);
long long ans = 0;
for (int index = 0; index < Edge.size(); ++index) {
ans += 2 * val[index];
point_to[Edge[index].x - 1].push_back({ Edge[index].y - 1,val[index] });
point_to[Edge[index].y - 1].push_back({ Edge[index].x - 1,val[index] });
}
dfs(0, -1);
return ans - max_l;
}
};</int></point>