結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:04:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 176 ms / 3,000 ms |
コード長 | 2,116 bytes |
コンパイル時間 | 1,006 ms |
コンパイル使用メモリ | 115,920 KB |
最終ジャッジ日時 | 2025-01-07 15:54:30 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <chrono> #define _USE_MATH_DEFINES #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <iterator> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <string> #include <tuple> #include <utility> #include <vector> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() const int INF = 0x3f3f3f3f; const long long LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; /*-------------------------------------------------*/ using CostType = long long; struct Edge { int src, dst; CostType cost; Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {} inline bool operator<(const Edge &rhs) const { return cost != rhs.cost ? cost < rhs.cost : dst != rhs.dst ? dst < rhs.dst : src < rhs.src; } inline bool operator<=(const Edge &rhs) const { return cost <= rhs.cost; } inline bool operator>(const Edge &rhs) const { return cost != rhs.cost ? cost > rhs.cost : dst != rhs.dst ? dst > rhs.dst : src > rhs.src; } inline bool operator>=(const Edge &rhs) const { return cost >= rhs.cost; } }; int n; vector<Edge> graph[200000]; long long ans = 0; int dfs(int par, int ver) { int res = 1; for (Edge e : graph[ver]) if (e.dst != par) { int child = dfs(ver, e.dst); res += child; ans += e.cost * child * (n - child); // cout << e.cost << ' ' << child << '\n'; } return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); // freopen("input.txt", "r", stdin); cin >> n; REP(_, n - 1) { int u, v, w; cin >> u >> v >> w; --u; --v; graph[u].emplace_back(Edge(u, v, w)); graph[v].emplace_back(Edge(v, u, w)); } dfs(-1, 0); cout << ans * 2 << '\n'; return 0; }