結果
問題 | No.872 All Tree Path |
ユーザー |
|
提出日時 | 2019-08-30 21:36:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 130 ms / 3,000 ms |
コード長 | 871 bytes |
コンパイル時間 | 1,902 ms |
コンパイル使用メモリ | 176,560 KB |
実行使用メモリ | 32,128 KB |
最終ジャッジ日時 | 2024-11-21 22:11:14 |
合計ジャッジ時間 | 3,767 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) #define range(a) a.begin(), a.end() using namespace std; using ll = long long; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); int N; cin >> N; vector<vector<pair<ll, ll>>> G(N); rep(i, N - 1) { int a, b, c; cin >> a >> b >> c; a--; b--; G[a].emplace_back(b, c); G[b].emplace_back(a, c); } vector<int> size(N); ll ans = 0; auto dfs = [&](auto dfs, int u, int p) -> void { size[u]++; for (auto e : G[u]) if (e.first != p) { dfs(dfs, e.first, u); size[u] += size[e.first]; } for (auto e : G[u]) if (e.first != p) { ans += (ll)e.second * size[e.first] * (N - size[e.first]); } }; dfs(dfs, 0, -1); cout << ans*2 << endl; }