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

· · 题解

纪念一下，场切了一个黄。

分析

首先，我们从上到下考虑。根的两个儿子，必有一个涂色，一个不涂，如果都不涂色的话就不是最优情况了，于是就是剩下没有涂色的一个儿子的情况了。那一个儿子的子树中，他又是根了，一样的，根的两个儿子，必有一个涂色，一个不涂，如果都不涂色的话就不是最优情况了，于是就这样递推下去了。根据递推的方案，只有有至少一个节点儿子数量只有一个才可能有解，并且可以通过递推过程快速看出，这是一个充要条件。

代码

// contest 329669 MX-X29 欧尼恩赛 2 
// problem B 双色二叉树
// 预期得分：100
#include<stdio.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        bool f=0;
        for(int i=1;i<=n;++i){
            int a,b;
            scanf("%d%d",&a,&b);
            if(a==b&&b==0)continue;
            if(a==0||b==0){
                f=1;
            }
        } 
        if(f==1)puts("Yes");
        else puts("No");
    }
    return 0;
}