結果
問題 | No.872 All Tree Path |
ユーザー |
|
提出日時 | 2019-09-01 02:37:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 289 ms / 3,000 ms |
コード長 | 1,466 bytes |
コンパイル時間 | 1,181 ms |
コンパイル使用メモリ | 106,280 KB |
実行使用メモリ | 37,552 KB |
最終ジャッジ日時 | 2024-11-26 10:31:13 |
合計ジャッジ時間 | 5,233 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <cstdio>#include <iostream>#include <string>#include <sstream>#include <stack>#include <algorithm>#include <cmath>#include <queue>#include <map>#include <set>#include <cstdlib>#include <bitset>#include <tuple>#include <assert.h>#include <fstream>#include <bitset>template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }const long long INF = 1LL << 60;const long long MOD = 1000000007LL;const long long MAX = 500000LL;using namespace std;typedef unsigned long long ull;typedef long long ll;ll N;vector<vector<pair<ll,ll>>> g1;vector<ll> g2;vector<ll> d;ll dfs(ll x, ll pre, ll cur) {ll res = 0;d[x] = cur;for (pair<ll,ll> xx : g1[x]) {if (xx.first == pre) continue;res += dfs(xx.first, x, cur + 1) + 1;}return g2[x] = res;}int main(){cin >> N;g1.resize(N);g2 = vector<ll>(N, 0);d.resize(N);vector<tuple<ll, ll, ll>> vt(N - 1);for (ll i = 0; i < N - 1; i++) {ll u, v, w;cin >> u >> v >> w;u--;v--;vt[i] = make_tuple(u, v, w);g1[u].push_back(make_pair(v, w));g1[v].push_back(make_pair(u, w));}dfs(0, -1, 0);ll res = 0;for (ll i = 0; i < N - 1; i++) {ll u, v, w;tie(u, v, w) = vt[i];if (d[u] > d[v]) {swap(u, v);}ll l = N - g2[v] - 1;ll r = g2[v] + 1;res += w * l * r * 2;}cout << res << endl;return 0;}