結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2021-01-28 00:02:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 253 ms / 3,000 ms |
コード長 | 1,257 bytes |
コンパイル時間 | 1,625 ms |
コンパイル使用メモリ | 170,324 KB |
実行使用メモリ | 34,432 KB |
最終ジャッジ日時 | 2024-06-25 01:11:49 |
合計ジャッジ時間 | 4,515 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using Graph = vector<vector<int>>;int depth[200005]; //depth[i]=頂点iの深さint par[200005];//par[i]=頂点iの親int subtree_size[200005];//部分木のサイズint u[200005];int v[200005];int w[200005];void dfs(Graph &G, int v, int p, int d){depth[v] = d;par[v] = p;for(auto nv : G[v]){if(nv==p)continue;dfs(G, nv, v, d+1);}// 帰りがけ時に、部分木サイズを求めるsubtree_size[v] = 1; // 自分自身for (auto c : G[v]) {if (c == p) continue;subtree_size[v] += subtree_size[c]; // 子のサイズを加える}}int main(){int n; cin >> n;Graph G(n);for(int i = 0; i < n-1; i++){ //木の辺の数はn-1int a, b, c; cin >> a >> b >> c;a--, b--;G[a].push_back(b);G[b].push_back(a);u[i] = a; v[i] = b; w[i] = c;}int root = 0; // 根を0に設定dfs(G, root, -1, 0);ll ans = 0;for(int i = 0; i < n-1; i++){ll num = 0; //num:根から遠い方の頂点を親とする部分木のサイズif(depth[u[i]]>depth[v[i]]) num = (ll)subtree_size[u[i]];else num = subtree_size[v[i]];ans += w[i]*2*num*((ll)n-num);}cout << ans << endl;return 0;}