結果
問題 | No.872 All Tree Path |
ユーザー |
|
提出日時 | 2019-09-01 05:34:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 224 ms / 3,000 ms |
コード長 | 645 bytes |
コンパイル時間 | 656 ms |
コンパイル使用メモリ | 73,828 KB |
実行使用メモリ | 40,756 KB |
最終ジャッジ日時 | 2024-11-27 06:02:37 |
合計ジャッジ時間 | 4,276 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
main.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 28 | main() | ^~~~
ソースコード
#include<iostream>#include<vector>using namespace std;int N;vector<pair<int,int> >G[2<<17];long ans;pair<long,int>dfs(int u,int p){vector<pair<long,int> >A;int cnt=1;for(pair<int,int>q:G[u]){int v=q.first;if(v==p)continue;pair<long,int>r=dfs(v,u);r.first+=q.second*r.second;A.push_back(r);cnt+=r.second;}long sum=0;for(pair<long,int>q:A){sum+=q.first;ans+=q.first*(cnt-q.second);}return make_pair(sum,cnt);}main(){cin>>N;for(int i=1;i<N;i++){int u,v,w;cin>>u>>v>>w;u--,v--;G[u].push_back(make_pair(v,w));G[v].push_back(make_pair(u,w));}dfs(0,-1);cout<<ans*2<<endl;}