結果
問題 | No.872 All Tree Path |
ユーザー |
|
提出日時 | 2019-08-30 23:41:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 254 ms / 3,000 ms |
コード長 | 795 bytes |
コンパイル時間 | 617 ms |
コンパイル使用メモリ | 70,144 KB |
実行使用メモリ | 30,208 KB |
最終ジャッジ日時 | 2024-11-22 04:32:03 |
合計ジャッジ時間 | 3,501 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <iostream>#include <vector>const int MAXN = 212345;std::vector<int> g[MAXN];int es[MAXN][3];int sz[MAXN];void dfs(int cur, int par) {sz[cur] = 1;for (int dst: g[cur]) {if (dst == par) continue;dfs(dst, cur);sz[cur] += sz[dst];}}int main() {int N;std::cin >> N;for (int i = 0; i < N - 1; ++i) {int u, v, w;std::cin >> u >> v >> w;--u;--v;es[i][0] = u;es[i][1] = v;es[i][2] = w;g[u].push_back(v);g[v].push_back(u);}dfs(0, -1);long long ans = 0;for (int i = 0; i < N - 1; ++i) {long long sz0 = sz[es[i][0]];long long sz1 = sz[es[i][1]];if (sz0 > sz1) ans += sz1 * (N - sz1) * es[i][2];else ans += sz0 * (N - sz0) * es[i][2];}std::cout << ans * 2 << std::endl;}