题解：CF1994E Wooden Game

NaPF6 · 2025-10-28 21:53:58 · 题解

首先，对于每一棵树，它的形态其实是不重要的。

我们只需要一直删叶子结点就能取到这棵树大小及以下的所有值。

因此，对于每一棵树，我们可以直接枚举一棵树取到什么值，最后取最大值即可。

这里可能会有一个问题，为什么一棵树的权值是它拆分开来的权值的或，我们却只枚举了一个值，不用管其他的呢？

这是因为对于一些数 a_i 来说，一定满足 \bigvee{a_i}\le\sum{a_i}，所以对于任意一种对树的拆分，它的权值或一定会在后面被枚举到。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int T,n,siz[N],ans;
void solve(){
    cin>>n;
    ans=0;
    for(int i=1,tmp;i<=n;i++){
        cin>>siz[i];
        for(int j=1;j<siz[i];j++){int x;cin>>x;}
        tmp=ans;
        for(int j=1;j<=siz[i];j++)ans=max(ans,tmp|j);
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--)solve();
    return 0;
}