結果
問題 | 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 1000000000000int 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;}