結果

問題 No.872 All Tree Path
ユーザー fine
提出日時 2019-08-30 21:53:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 181 ms / 3,000 ms
コード長 782 bytes
コンパイル時間 1,823 ms
コンパイル使用メモリ 171,860 KB
実行使用メモリ 32,792 KB
最終ジャッジ日時 2024-11-21 23:01:55
合計ジャッジ時間 4,309 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, ll>;
ll solve(int cur, int par, vector< vector<P> >& g, ll& ans) {
ll n = g.size();
ll res = 1;
for (P& e : g[cur]) {
if (e.first == par) continue;
ll num = solve(e.first, cur, g, ans);
res += num;
ans += e.second * num * (n - num) * 2;
}
return res;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector< vector<P> > g(n);
for (int i = 1; i < n; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
u--; v--;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
ll ans = 0;
solve(0, -1, g, ans);
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0