結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2019-08-30 21:57:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 903 ms / 3,000 ms |
コード長 | 1,181 bytes |
コンパイル時間 | 1,974 ms |
コンパイル使用メモリ | 184,864 KB |
実行使用メモリ | 41,088 KB |
最終ジャッジ日時 | 2024-11-21 23:15:18 |
合計ジャッジ時間 | 9,863 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000000000 int main(){ int N; cin>>N; vector<vector<pair<int,int>>> E(N,vector<pair<int,int>>()); vector<int> jisuu(N,0); for(int i=0;i<N-1;i++){ int a,b,w; cin>>a>>b>>w; a--;b--; E[a].emplace_back(b,w); E[b].emplace_back(a,w); jisuu[a]++; jisuu[b]++; } queue<int> Q; for(int i=0;i<N;i++){ if(jisuu[i]==1)Q.push(i); } map<pair<int,int>,int> M; while(Q.size()!=0){ int now = Q.front(); Q.pop(); int cnt = 1; int ind = -1; for(int i=0;i<E[now].size();i++){ if(M[make_pair(now,E[now][i].first)]==0){ ind = E[now][i].first; } else{ cnt+=M[make_pair(now,E[now][i].first)]; } } if(ind==-1)continue; M[make_pair(now,ind)]=cnt; M[make_pair(ind,now)]=cnt; jisuu[ind]--; if(jisuu[ind]==1){ Q.push(ind); } } long long ans = 0; for(int i=0;i<N;i++){ for(int j=0;j<E[i].size();j++){ long long a = M[make_pair(i,E[i][j].first)]; long long x = a*(N-a); x *= E[i][j].second; ans += x; } } cout<<ans<<endl; return 0; }