結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:03:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 237 ms / 3,000 ms |
コード長 | 1,150 bytes |
コンパイル時間 | 1,626 ms |
コンパイル使用メモリ | 172,952 KB |
実行使用メモリ | 29,824 KB |
最終ジャッジ日時 | 2024-11-21 23:33:48 |
合計ジャッジ時間 | 4,620 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<ll, ll> P;typedef pair<ll, P> P3;typedef pair<P, P> PP;constexpr ll MOD = ll(1e9 + 7);constexpr int IINF = INT_MAX;constexpr ll LLINF = LLONG_MAX;constexpr int MAX_N = int(1e5) + 5;constexpr double EPS = 1e-9;constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};#define REP(i, n) for (int i = 0; i < n; i++)#define REPR(i, n) for (int i = n; i >= 0; i--)#define SORT(v) sort((v).begin(), (v).end())#define SORTR(v) sort((v).rbegin(), (v).rend())#define ALL(v) (v).begin(), (v).end()vector<vector<P> > g;ll n;ll ans = 0;ll dfs(int v, int p){ll res = 0;for(auto e : g[v]){int u = e.first;if(u == p) continue;ll cnt = dfs(u, v);ans += cnt*(n-cnt)*e.second;res += cnt;}return res+1;}int main() {cin >> n;g.resize(n);for(int i=0;i<n-1;i++){ll u, v, w;cin >> u >> v >> w;u--; v--;g[u].push_back({v, w});g[v].push_back({u, w});}dfs(0,-1);cout << ans*2 << endl;return 0;}