题意简述

有一个森林，每次可以从任意一棵树中删除一个子树，进行任意多次，直到所有树被完全删除。每次删除的子树大小是某个正整数。求所有删除子树大小的按位或的最大值。

转化

对于一棵大小为 $n$ 的树，我们可以通过若干次操作将其完全删除，每次删除一个子树。这些子树的大小构成一个正整数序列，其总和为 $n$。因此，问题转化为：有 $k$ 个整数 $n_1, n_2, \dots, n_k$（每棵树的大小），你需要将每个 $n_i$ 拆分成若干个正整数之和，使得所有正整数的按位或最大。求该最大 OR。

贪心求解

我们可以按从大到小的顺序处理这些整数。设当前答案为 $ans$（初始为 $0$）。对于当前的 $x$（一棵树的大小），从高位向低位扫描（由于 $x\le 10^6<2^{20}$，扫描 $0$ 到 $23$ 位即可）：

• 若 $x$ 的当前位为 $0$，跳过。
• 若 $ans$ 的当前位为 $0$，直接将 $ans$ 的这一位置为 $1$（即 $ans \mid= (1 \ll h)$）。
• 若 $ans$ 的当前位已经是 $1$，且 $x$ 的这一位也是 $1$，这意味着我们可以将 $x$ 的这一位“拆掉”，并用剩余部分将 $ans$ 的所有低于该位的位全部变成 $1$。此时执行 ans |= (1 << h) - 1，并停止处理当前 $x$（跳出循环）。

遍历完所有 $x$ 后，$ans$ 即为最大 OR。

正确性简述

• 当 $ans$ 的某一位已经是 $1$ 而 $x$ 的该位也是 $1$ 时，我们不能通过直接 OR 获得更大收益（因为该位已置 $1$）。但我们可以利用 $x$ 来“补充”更低的位。因为 $x$ 可以被任意拆分，我们可以将其拆成 $2^h$ 和 $x - 2^h$。其中 $2^h$ 对答案无贡献，而剩余部分 $x-2^h \le 2^h-1$，它的二进制表示完全在 $h$ 位以下。因此我们可以通过这次拆分将所有低于 $h$ 的位全部变成 $1$。这正是代码中 ans |= (1<<h)-1 的含义。
• 按从大到小处理保证了贪心选择不会降低最终结果的位数。
• 这样每个数至多贡献一次“低位填满”操作，整体复杂度 $O(k \log \max n)$。

为什么树的具体结构无关？

对于任意一棵有根树，我们总能通过选择合适的删除顺序，获得任意一种将 $n$ 拆分成若干个正整数的方案。因此只需保留树的大小，忽略父节点序列。算法直接读取每棵树的大小即可。

时间复杂度

总节点数 $\sum n \le 10^6$，加上排序 $O(k \log k)$，总复杂度 $O(10^6 \log 10^6)$，在时限内足以通过。

参考代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int k;
    cin >> k;
    vector<int> a(k);
    for (int i = 0; i < k; ++i) {
        cin >> a[i];
        // 忽略树的结构，直接跳过父节点
        for (int j = 0; j < a[i] - 1; ++j) {
            int trash;
            cin >> trash;
        }
    }
    sort(a.begin(), a.end(), greater<>());
    int ans = 0;
    for (auto x : a) {
        for (int h = 23; h >= 0; --h) {
            int ca = ans >> h & 1, cx = x >> h & 1;
            if (cx == 0) continue;
            if (ca == 0) ans |= 1 << h;
            else {
                ans |= (1 << h) - 1;
                break;
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
}