結果

問題 No.1843 Tree ANDistance
ユーザー kenta255kenta255
提出日時 2022-02-26 18:05:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 4,175 bytes
コンパイル時間 3,646 ms
コンパイル使用メモリ 230,552 KB
実行使用メモリ 39,300 KB
最終ジャッジ日時 2023-09-17 20:15:18
合計ジャッジ時間 14,422 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef priority_queue<ll, vector<ll>, greater<ll> > PQ;
//#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)  // int範囲に注意 llより早い
#define FORR(I,A,B) for(int I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*b);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87); pairもいける
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
ll ketawa(ll a){ll r=0;while(a){r+=a%10;a/=10;}return r;}
#define num_l(a,v) POSL(a,v) //v未満の要素数
#define num_eql(a,v) POSU(a,v) //v以下の要素数
#define num_h(a,v) (a.size() - POSU(a,v)) //vより大きい要素数
#define num_eqh(a,v) (a.size() - POSL(a,v)) //v以上の要素数


vector<int> Centroid(const vector< vector<int> > &G){
	queue<int> leaf;
	const int root = 0;
	const int N = G.size();
	vector<int> cnt(N,0),pa(N,-1);
	FOR(i,0,N){
		cnt[i] = G[i].size();
		if(G[i].size() == 1 && i != root){
			leaf.push(i);
		}
	}
	vector<int> size_sub_tree(N,1);
	while(leaf.size()){
		int u = leaf.front();
		leaf.pop();
		for(int v:G[u]){
			if(cnt[v] >= 2){
				size_sub_tree[v] += size_sub_tree[u];
				cnt[v]--;
				if(cnt[v] == 1 && v!=root){
					leaf.push(v);
					pa[u] = v;
				}
			}
		}
	}
	vector<int> res;
	FOR(i,0,N){
		bool ok = (N-size_sub_tree[i]) <= N/2;
		for(auto u:G[i]){
			if(u == pa[i]) continue;
			ok &= size_sub_tree[u] <= N/2;
		}
		if(ok) res.push_back(i);
	}
	return res;
}

int main(){
	int N;
	cin >> N;
	vector<vector<int>> G(N),Gc(N);
	FOR(i,0,N-1){
		int u,v,c;
		cin >> u >> v >> c;
		G[u-1].push_back(v-1);
		G[v-1].push_back(u-1);
		Gc[u-1].push_back(c);
		Gc[v-1].push_back(c);
	}
	queue< vector<vector<int>> > QG;
	queue< vector<vector<int>> > QGc;
	QG.push(G); G.clear();
	QGc.push(Gc); Gc.clear();

	ll ans = 0;
	while(QG.size()){
		int center = Centroid(QG.front())[0];
		auto g = QG.front();
		QG.pop();
		auto gc = QGc.front();
		QGc.pop();
		
		vector<ll> cnt(64,0); // ibit目が1のやつの個数
		for(int i=0;i<g[center].size();i++){
			map<int,int> number;
			int k = 1;
			// g[center][i]を根とする部分木で計算
			vector<ll> and_(N,-1);
			and_[ g[center][i] ] = gc[center][i];
			number[ g[center][i] ] = k++;
			and_[ center ] = 0;
			queue<int> v;
			v.push(g[center][i]);
			vector<vector<int>> makeG,makeGc;
			vector<int> use;
			use.push_back(g[center][i]);
			while(v.size()){
				int from = v.front(); v.pop();
				//cout << "From = " << from << endl;
				for(int j=0;j<(int)g[from].size();j++){
					int to = g[from][j];
					if(and_[to] >= 0)continue;
					and_[to] = and_[from] & gc[from][j];
					v.push(to);
					//cout << "Hey" << endl;
					if(number[from] == 0){ number[from] = k++; use.push_back(from); }
					if(number[ to ] == 0){ number[ to ] = k++; use.push_back(to); }
					makeG.resize(k-1);
					makeGc.resize(k-1);
					makeG[ number[from]-1 ].push_back( number[ to ]-1 );
					makeG[ number[ to ]-1 ].push_back( number[from]-1 );
					makeGc[ number[from]-1 ].push_back( gc[center][j] );
					makeGc[ number[ to ]-1 ].push_back( gc[center][j] );
				}
			}
			if(k>2)QG.push(makeG);
			if(k>2)QGc.push(makeGc);
			//cout<<"USE:";for(auto x:use)cout<<x<<" ";cout<<endl;
			for(auto u:use){
				(ans += and_[u]) %= MOD;
				for(int j=0;j<33;j++){
					if(and_.at(u) & (1LL<<j)){
						(ans += (1LL<<j) * cnt[j]%MOD) %= MOD;
					}
				}
			}
			for(auto u:use){
				for(int j=0;j<33;j++){
					if(and_[u] & (1LL<<j)){
						cnt.at(j)++;
					}
				}
			}
		}
	}
	cout << ans << endl;
}
0