結果
問題 | 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;}