2017BUPT校赛 H-Black-white Tree

H. Black-white Tree 2017- BUPT Collegiate Programming Contest - sync

时间限制 1000 ms  内存限制 65536 KB

题目描述

Alice and Bob take turns to perform operations on a rooted tree of size n. The tree is rooted at node 1, with each node colored either black or white. In each turn a player can choose a black node and inverse the color of all nodes in the node's subtree. If any player can't perform the operation, he loses. Now Alice plays first, who will win if both players adopt the best strategy?

输入格式

The first line contains only one integer T(1≤T≤10), which indicates the number of test cases.
For each test case:

• The first line contains an integer n(1≤n≤100000), indicating the size of the tree;
• The second line contains n integers a1,a2,...,an(ai=0,1), representing the color of the ith node where 0 indicates white and 1 indicates black;
• In the next n−1 lines, each line contains two integers u,v(1≤u,v≤n), indicating there is an edge between node u and node v.

 

输出格式

For each test case, output Alice or Bob to show the winner.

输入样例

3
3
1 1 1
1 2
1 3
3
1 1 0
1 2
1 3
3
0 0 0
1 2
1 3

输出样例

Alice
Bob
Bob

每棵树的“奇偶性”都是确定的，只需看最初的树是奇还是偶即可。

对于一棵树，如果根节点为1，那么如果以根结点的子节点为根的子树中有偶数个偶树，这个树就是奇树；如果根结点为0，那么如果以根节点的子节点为根的子树中有奇数个奇树，这个树就是奇树。其余情况为偶树。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <stack>
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
const int MAX=1e5+5;
const int INF=1e9+5;
using namespace std;
typedef pair<int,int> pii;
vector <int>edge[MAX];
int x,y;
int t,n;
int a[MAX];
int check(int x,int from)
{
    int b[2]={0};
    int to;
    for(int i=0;i<edge[x].size();i++)
    {
        to=edge[x][i];
        if(to==from)
            continue;
        b[check(to,x)]^=1;
    }
    if((a[x]&&!b[0])||(!a[x]&&b[1]))
        return 1;
    else return 0;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),edge[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            edge[x].push_back(y);edge[y].push_back(x);
        }
        if(check(1,0))
            printf("Alice\n");
        else
            printf("Bob\n");
    }
}