結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:40:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 91 ms / 3,000 ms |
コード長 | 1,573 bytes |
コンパイル時間 | 792 ms |
コンパイル使用メモリ | 81,400 KB |
実行使用メモリ | 19,344 KB |
最終ジャッジ日時 | 2024-11-22 01:23:44 |
合計ジャッジ時間 | 2,612 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>using namespace std;using ll = long long;ll r = 0;struct Graph {struct Vertex { int n, k; ll s; };struct Edge { int i, n, c; };Graph(int n, int m) : v(n, { -1, 0, 0 }), e(m), n(n), m(0) {}void add_edge(int i, int j, int c) {e[m] = { j, v[i].n, c };v[i].n = m;m++;}pair<ll, int> dfs(int i, int c, int p) {ll s = c;int k = 1;for (int j = v[i].n; j >= 0; j = e[j].n) {Edge &o = e[j];if (o.i == p) continue;auto p = dfs(o.i, c + o.c, i);s += p.first;k += p.second;}return { v[i].s = s, v[i].k = k };}void dfs2(int i, int c, ll s, int p) {ll t = (v[i].s - (ll)c * v[i].k) + s;r += t;for (int j = v[i].n; j >= 0; j = e[j].n) {Edge &o = e[j];if (o.i == p) continue;dfs2(o.i, c + o.c, t - (v[o.i].s - (ll)c * v[o.i].k) + (ll)o.c * (n - v[o.i].k), i);}}vector<Vertex> v;vector<Edge> e;int n, m;};int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;Graph g(n, (n - 1) * 2);for (int i = 0; i < n - 1; i++) {int a, b, c;cin >> a >> b >> c;a--; b--;g.add_edge(a, b, c);g.add_edge(b, a, c);}g.dfs(0, 0, -1);g.dfs2(0, 0, 0, -1);cout << r << endl;return 0;}