結果
問題 | No.1207 グラフX |
ユーザー |
![]() |
提出日時 | 2020-07-29 13:17:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 484 ms / 2,000 ms |
コード長 | 1,863 bytes |
コンパイル時間 | 1,821 ms |
コンパイル使用メモリ | 175,756 KB |
実行使用メモリ | 51,712 KB |
最終ジャッジ日時 | 2024-07-04 21:51:48 |
合計ジャッジ時間 | 20,462 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include<bits/stdc++.h>//事前処理とUnion-Findusing std::cin;using std::cout;using std::endl;using std::vector;using ll=long long;const int MOD=1e9+7;struct Union_Find{int N;vector<int> par;Union_Find(int n):N(n){par.resize(N);for(int i=0;i<N;i++) par[i]=i;}int root(int X){if(par[X]==X) return X;return par[X]=root(par[X]);}bool same(int X,int Y){return root(X)==root(Y);}void unite(int X,int Y){X=root(X),Y=root(Y);if(X!=Y) par[X]=Y;}};ll modpow(ll X,ll Y){ll ret=1;while(Y>0){if(Y%2){ret*=X;ret%=MOD;}Y/=2;X*=X;X%=MOD;}return ret;}void dfs(int N,int X,int now,vector<bool> &seen,vector<vector<int>> &edge,vector<vector<int>> &weight,vector<int> &subtree,ll &ans){seen[now]=1;for(int i=0;i<edge[now].size();i++){int next=edge[now][i];if(!seen[next]){dfs(N,X,next,seen,edge,weight,subtree,ans);subtree[now]+=subtree[next];ans+=modpow(X,weight[now][i])*subtree[next]%MOD*(N-subtree[next])%MOD;ans%=MOD;}}subtree[now]++;}int main(){int N,M,X; cin>>N>>M>>X;vector<vector<int>> edge(N),weight(N);Union_Find UF(N);//最小全域木を作るfor(int i=0;i<M;i++){int x,y,z; cin>>x>>y>>z;if(!UF.same(x-1,y-1)){UF.unite(x-1,y-1);edge[x-1].push_back(y-1);edge[y-1].push_back(x-1);weight[x-1].push_back(z);weight[y-1].push_back(z);}}//dfsで各辺が経路になる回数を数えていくvector<int> subtree(N);vector<bool> seen(N);ll ans=0;dfs(N,X,0,seen,edge,weight,subtree,ans);cout<<ans<<endl;}