1 条题解
-
0
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 500000 + 5; int n, s; struct Edge { int v, w; }; vector<Edge> e[MAXN]; int dp[MAXN], len[MAXN]; void dfs(int u, int fa) { int maxLen = 0; dp[u] = 0; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].v; int w = e[u][i].w; if (v == fa) continue; dfs(v, u); maxLen = max(maxLen, w + len[v]); dp[u] += dp[v]; } len[u] = maxLen; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].v; int w = e[u][i].w; if (v == fa) continue; dp[u] += maxLen - (w + len[v]); } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> s; for (int i = 1; i <= n - 1; i++) { int u, v, w; cin >> u >> v >> w; e[u].push_back((Edge){v, w}); e[v].push_back((Edge){u, w}); } dfs(s, 0); cout << dp[s]; return 0; }
- 1
信息
- ID
- 1954
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 18
- 已通过
- 8
- 上传者