結果
問題 | No.1843 Tree ANDistance |
ユーザー |
![]() |
提出日時 | 2022-02-21 00:10:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 242 ms / 2,000 ms |
コード長 | 1,781 bytes |
コンパイル時間 | 1,656 ms |
コンパイル使用メモリ | 171,600 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-29 10:59:04 |
合計ジャッジ時間 | 6,803 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct UnionFind{ vector<int> parent; vector<int> numberOfElements;//根ノードのみ有効 UnionFind(int n){ parent.resize(n); numberOfElements.resize(n); for(int i=0;i<n;++i){ parent[i]=-1; numberOfElements[i]=1; } } int find(int a){ vector<int> path(0); int pointer=a; while(parent[pointer]!=-1){ path.push_back(pointer); pointer=parent[pointer]; } for(int i:path){ parent[i]=pointer; } return pointer; } void unite(int a,int b){ int p=find(a); int q=find(b); if(p==q){ return; } if(numberOfElements[p]<numberOfElements[q]){ parent[p]=q; numberOfElements[q]+=numberOfElements[p]; }else{ parent[q]=p; numberOfElements[p]+=numberOfElements[q]; } } }; int main(){ int N,mod=pow(10,9)+7; cin>>N; int edges[N-1][3]; long long cur=1,ans=0; for(int i=0;i<N-1;++i){ for(int j=0;j<3;++j){ cin>>edges[i][j]; edges[i][j]-=(j<2); } } for(int i=0;i<32;++i){ long long temp=0; UnionFind U(N); for(int j=0;j<N-1;++j){ if(edges[j][2]%2){ U.unite(edges[j][0],edges[j][1]); } } for(int j=0;j<N-1;++j){ if(U.find(j)==j){ long long n=U.numberOfElements[j]; temp=(temp+n*(n-1)/2)%mod; } } for(int j=0;j<N-1;++j){ edges[j][2]>>=1; } ans=(ans+temp*cur)%mod; cur=(cur*2)%mod; } cout<<ans<<endl; }