結果

問題 No.872 All Tree Path
ユーザー merom686
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0