結果
問題 | No.872 All Tree Path |
ユーザー |
|
提出日時 | 2019-11-27 14:06:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 287 ms / 3,000 ms |
コード長 | 1,415 bytes |
コンパイル時間 | 1,767 ms |
コンパイル使用メモリ | 175,320 KB |
実行使用メモリ | 28,160 KB |
最終ジャッジ日時 | 2024-11-08 03:06:45 |
合計ジャッジ時間 | 5,067 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long ;using P = pair<ll, ll>;using Vec = vector<ll>;#define FOR(i, m, n) for(ll (i) = (m); (i) < (n); (i)++)#define FORN(i, m, n) for(ll (i) = (m); (i) <= (n); (i)++)#define FORR(i, m, n) for(ll (i) = (m); (i) >= (n); (i)--)#define rep(i, n) FOR(i, 0, n)#define repn(i, n) FORN(i, 1, n)#define repr(i, n) FORR(i, n, 0)#define repnr(i, n) FORR(i, n, 1)#define co(n) cout << (n) << endl#define cosp(n) cout << (n) << ' '#define setp(n) cout << fixed << setprecision(n);#define all(s) (s).begin(), (s).end()#define pb push_back#define mp make_pair#define fs first#define sc secondconst ll INF = 1e9+1;const ll LINF = 1e18+1;const ll MOD = 1e9+7;//const ll MOD = 998244353;const double PI = acos(-1);const double EPS = 1e-9;vector<vector<P> > tree;Vec child_num;ll ans = 0;ll n = 0;void dfs(ll node, ll par){ll cost = 0;for(P i : tree[node]){if(i.fs != par) dfs(i.fs, node);else cost = i.sc;}if(node != par){child_num[par] += child_num[node];ans += child_num[node]*(n-child_num[node])*cost*2;}}int main(void){cin >> n;tree.resize(n);child_num.resize(n);fill(all(child_num), 1);rep(i, n-1){ll u, v, w;cin >> u >> v >> w;u--, v--;tree[u].pb(mp(v, w));tree[v].pb(mp(u, w));}dfs(0, 0);co(ans);return 0;}