結果
問題 | No.1843 Tree ANDistance |
ユーザー |
👑 ![]() |
提出日時 | 2021-12-09 01:11:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 178 ms / 2,000 ms |
コード長 | 1,527 bytes |
コンパイル時間 | 1,948 ms |
コンパイル使用メモリ | 196,428 KB |
最終ジャッジ日時 | 2025-01-26 07:03:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;using std::cout;using std::cin;using std::endl;using ll=long long;const ll mod=1e9+7;#define rep(i,a) for (int i=0;i<a;i++)namespace po167{struct UFtree{std::vector<int> wei;int component;UFtree(int n):par(n),wei(n),component(n){for(int i=0;i<n;i++){wei[i]=1,par[i]=i;}}void intialize(){for(int i=0;i<(int) par.size();i++){wei[i]=1,par[i]=i;}component=(int)par.size();}//根っこを返すint root(int a){if(a==par[a]) return a;return par[a]=root(par[a]);}//trueなら1,falseなら0int same(int a,int b){if(root(a)==root(b)) return 1;else return 0;}//a,bが違う根っこの元なら結合する,結合したらtrueを返すbool unite(int a,int b){a=root(a),b=root(b);if(a==b) return false;if(wei[a]<wei[b]) std::swap(a,b);par[b]=a;wei[a]+=wei[b];component--;return true;}private:std::vector<int> par;};}using po167::UFtree;int main() {int N;cin>>N;vector<int> A(N-1),B(N-1),C(N-1);rep(i,N-1){cin>>A[i]>>B[i]>>C[i];A[i]--,B[i]--;}ll ans=0;UFtree T(N);rep(i,32){ll tmp=0;T.intialize();rep(j,N-1){if(C[j]&(1<<i)) T.unite(A[j],B[j]);}rep(i,N){if(T.root(i)==i){tmp+=((ll)(T.wei[i])*(ll)(T.wei[i]-1))/2;}}tmp%=mod;tmp*=(1ll<<i);ans+=tmp%mod;}cout<<(ans%mod+mod)%mod<<"\n";}