結果
問題 | No.872 All Tree Path |
ユーザー |
|
提出日時 | 2019-08-30 23:12:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 328 ms / 3,000 ms |
コード長 | 1,233 bytes |
コンパイル時間 | 2,151 ms |
コンパイル使用メモリ | 202,064 KB |
最終ジャッジ日時 | 2025-01-07 16:04:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))#define ALL(x) begin(x), end(x)using ll = long long;using namespace std;template<typename Functor> struct fix_type { Functor functor; template<typename... Args> decltype(auto) operator() (Args && ... args) const & { returnfunctor(functor, std::forward<Args>(args)...); } };template<typename Functor> fix_type<typename std::decay<Functor>::type> fix(Functor && functor) { return { std::forward<Functor>(functor) }; }int main() {// inputint n; cin >> n;vector<vector<pair<int, ll> > > g(n);REP (i, n - 1) {int u, v, w; cin >> u >> v >> w;-- u;-- v;g[u].emplace_back(v, w);g[v].emplace_back(u, w);}// solvell d = 0;fix([&](auto && self, int i, int parent) -> int {vector<int> sizes;for (auto edge : g[i]) {int j, cost; tie(j, cost) = edge;if (j == parent) continue;int size = self(self, j, i);sizes.push_back(size);d += 2ll * size * (n - size) * cost;}return accumulate(ALL(sizes), 0) + 1;})(0, -1);// outputcout << d << endl;return 0;}