CodeForces

分析

以下所有图片均来自官方题解。

首先初始就为白色的点不太好搞，考虑怎么样把它当成无色点。

假设 $A$ 是一个白色点，我们在它上面挂 $3$ 个新点：

可以发现这样子对游戏胜负没有影响。

可以这么考虑：如果白方把 $A$ 涂白了，那么黑方只能把 $B$ 涂黑。所以这就相当于多用一轮回到了给定的状态。

现在是一个没有颜色的树，考虑这上面的胜负情况。

显然黑色不可能赢，也就是说只可能白色获胜或者平局。

考虑白色获胜的情况有哪些：

• 存在一个节点，满足它的度数 $\geq 4$ 。

白色染最上面那个节点，然后就赢了。

• 存在一个节点，满足它的度数 $=3$ ，并且至少有 $2$ 个非叶子节点与它相邻。

白色染最上面那个点，然后在黑色染完之后再染一个相邻的非叶子节点，然后就赢了。

剩下的情况就只有一条链，左右两边可能挂了两个节点。

可以猜想，这种情况是平局。然后你就会 WA on #2 。

考虑下面这种情况：

可以发现这也是白色赢，原因是我们可以把上面的图看成下面的样子。

进一步扩展一下就是这样子：

• 如果树的形态是一条链左右两边各挂了两个节点，并且节点个数为奇数，那么白色获胜。

获胜方法就不讲了

另外可以证明，除了以上 $3$ 种情况都是平局。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000000+10;

struct Edge { int v,nxt; } e[N<<1];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int n,deg[N];
char str[N];

int main() {
    int T=read();
    while (T--) {
        memset(head,0,sizeof(int)*(n+1)),cnt=0;
        memset(deg,0,sizeof(int)*(n+1));

        n=read();
        for (re int i=1;i<n;++i) {
            int u=read(),v=read();
            addEdge(u,v),addEdge(v,u);
            ++deg[u],++deg[v];
        }
        scanf("%s",str+1);

        if (n<3) { puts("Draw"); continue; }
        if (n==3) {
            int sum=0;
            for (re int i=1;i<=3;++i) sum+=(str[i]=='W');
            puts(sum>=2?"White":"Draw");
            continue;
        }

        for (re int i=1;i<=n;++i) {
            if (str[i]!='W') continue;
            ++n,head[n]=0;
            addEdge(i,n),addEdge(n,i);
            ++deg[i],deg[n]=3;
        }

        int flag=0,s=0;
        for (re int i=1;i<=n;++i) {
            if (deg[i]>3) { flag=1; break; }
            if (deg[i]==3) {
                int sum=0;
                for (re int j=head[i];j;j=e[j].nxt)
                    if (deg[e[j].v]>=2) ++sum;
                if (sum>=2) { flag=1; break; }
                ++s;
            }
        }
        if (s==2&&(n&1)) flag=1;
        puts(flag?"White":"Draw");
    }
    return 0;
}