結果
問題 | No.1843 Tree ANDistance |
ユーザー |
|
提出日時 | 2022-02-18 21:28:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 2,007 bytes |
コンパイル時間 | 1,755 ms |
コンパイル使用メモリ | 139,092 KB |
最終ジャッジ日時 | 2025-01-27 23:41:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 38 |
ソースコード
#pragma GCC optimize("Ofast") #include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <cstdio> #include <ctime> #include <assert.h> #include <chrono> #include <random> #include <numeric> #include <set> #include <deque> #include <stack> #include <sstream> #include <utility> #include <cstring> #include <unordered_map> #include <unordered_set> #include <tuple> #include <array> #include <bitset> using namespace std; typedef long long int ll; typedef unsigned long long ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } inline double time() { return static_cast<double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9; } constexpr ll mod = 1e9+7; struct UnionFind{ vector<int> par,num; UnionFind(int n):par(n),num(n,1){ iota(par.begin(),par.end(),0); //include<numeric> } int find(int v){ return (par[v]==v)?v:(par[v]=find(par[v])); } void unite(int u,int v){ u=find(u),v=find(v); if(u==v)return; if(num[u]<num[v])swap(u,v); num[u]+=num[v]; par[v]=u; } bool same(int u,int v){ return find(u) == find(v); } int size(int v){ return num[find(v)]; } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; ll res = 0; vector<int> x(n-1),y(n-1),c(n-1); for(int i=0;i+1<n;i++){ cin >> x[i] >> y[i] >> c[i]; x[i]--; y[i]--; } for(int i=0;i<30;i++){ UnionFind uf(n); for(int j=0;j+1<n;j++){ if((1<<i)&c[j]){ uf.unite(x[j],y[j]); } } ll ad = 0; for(int j=0;j<n;j++){ if(uf.find(j) == j){ ad += (ll)(uf.size(j)) * (ll)(uf.size(j)-1) / 2; } } res += ad%mod*(1LL<<i)%mod; } cout << res%mod << endl; }