Codeforces #959 : E. Wooden Game

こちらも割とすんなり。
https://codeforces.com/contest/1994/problem/E

問題

根付き木がK個与えられる。
ここから、点を選んでSubTreeを切り落とす作業を任意回数行えるとする。
切り落としたSubTreeのサイズのbitwise-orの最大値を求めよ。

解法

実は細かい木の形状はどうでもよく、頂点数だけが問題。
葉から順に切り落とせば、狙ったbitを立てられるような値を選ぶことができる。

よって木を大きい順に並べ、bitwise-orが最大値になるようにサイズを減らしたうえでorを取って行けばよい。

int T;
int K;
int N[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>K;
		FOR(i,K) {
			cin>>N[i];
			FOR(j,N[i]-1) cin>>x;
		}
		sort(N,N+K);
		int cur=0;
		for(i=K-1;i>=0;i--) {
			x=N[i];
			int want=(1<<30)-1-cur;
			
			for(j=29;j>=0;j--) {
				if(want&(1<<j)) {
					if(x&(1<<j)) {
						cur|=1<<j;
					}
				}
				else if(x&(1<<j)) {
					x=(1<<30)-1;
				}
			}
		}
		cout<<cur<<endl;
	}
}

まとめ

木の形状がどうでもいいのが面白いな。