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

· · 题解

:::info[盲猜结论] 只要这颗树有一个节点有且仅有一个子节点，那么它一定满足条件，反之一定不满足条件。 :::

发现这棵树是个二叉树，发现对于一个拥有两个儿子的节点，将其一个子节点涂黑后即不用考虑该子节点的所有叶子。这样的话我们只要找到一颗根不需被涂黑的子树即可。易得如下几个图，可以得出上述结论：

显然，如果一个节点仅有一个子节点，那么这个节点不需涂色，只需将其子节点涂色即可。

如果一个有两个子节点的节点，其中一个子节点可以不涂色即可满足条件，那么自然可以让其另一个子节点涂色，即这个节点也满足不涂色的条件。如此递归，即根也可以满足不涂色的条件。

最终结论得证。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int l[N],r[N];
int n; 
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
    bool fl=0;
    for(int i=1;i<=n;i++)
        if(l[i]&&!r[i]||!l[i]&&r[i]) fl=1;
    if(fl) cout<<"Yes\n";
    else cout<<"No\n";  
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T; 
    while(T--) solve();
    return 0;
}