题解：P16831 【MX-X29-T2】『FeOI-6』双色二叉树

Fu_xuan_ · 2026-06-07 19:40:33 · 题解

题目传送门

思路

直接判断整棵树是不是满二叉树，是的话无解，不是的话有解。

证明：

先考虑必要性：

一棵高度为 h 的满二叉树 T ，设其根节点左右儿子子树为 T_A 和 T_B ，选取其中一个儿子为黑点，那么另一颗子树只能在它的左右儿子中选择一个点成为黑点，用下面的节点变成黑点来封锁整条路径，以此类推，直到叶子节点无法再使用孩子节点封锁此条路径，那么就无解了。

所以满二叉树必无解。

再考虑充分性：

一棵二叉树不是满二叉树 \Longleftrightarrow 这棵树存在单孩子节点。

设其为 u。

那么我们只要将 u 涂黑即可封锁其子树的所有节点，这就打破了满二叉树无法在满足约束的情况下进行有效封锁的问题。

所以非满二叉树必有解。

至此，我们得出有解的充要条件是整树是非满二叉树。

直接遍历树判断就行。

Code

#include <bits/stdc++.h>
using namespace std;
void slv(){
    int n;
    cin >> n;
    vector<int> l(n + 1), r(n + 1);
    for (int i = 1; i <= n; ++i){
        cin >> l[i] >> r[i];
    }
    vector<int> num(n + 1, 0);
    function<void(int)> dfs = [&](int u){
        if (!l[u] and !r[u]){
            num[u] = 1;
            return;
        }
        if (l[u]){
            dfs(l[u]);
        }
        if (r[u]){
            dfs(r[u]);
        }
        if (num[l[u]] == 1 and num[r[u]] == 1){
            num[u] = 1;
        }
    };
    dfs(1);
    cout << (!num[1] ? "Yes\n" : "No\n");
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--){
        slv();
    }
    return 0;
}