Tree-Tac-Toe

题意翻译

### 题目描述 给出一棵$N$个点的树，初始时某些节点是白色，其他节点没有颜色。 有两个人在树上博弈。每一回合，一方可以将一个没有颜色的点染成白色，然后另一方可以将一个没有颜色的点染成黑色。 如果在某次染色后树上存在三个点$ABC$满足有边$(A,B)(B,C)$、$ABC$都有颜色且颜色相同，则该颜色对应的人获胜。 假设两人绝顶聪明，问最后结果如何。 ### 输入格式 多组询问，第一行一个正整数$T (1 \leq T \leq 50000)$表示询问数 每组询问第一行一个正整数$n (1 \leq n \leq 500000 , \sum n \leq 500000)$表示树的点数 接下来$n-1$行每行两个正整数$u,v$表示树的一条边 最后一行一个长度为$n$、只包含`W`和`N`两种字符的字符串表示每个节点的颜色。字符串的第$i$个字符为`W`表示$i$号点初始为白色，否则初始时没有颜色。 ### 输出格式 对于每组询问输出一行，如果白色方胜利输出`White`，黑色方胜利输出`Black`，平局输出`Draw`。

题目描述

The tic-tac-toe game is starting on a tree of $ n $ vertices. Some vertices are already colored in white while the remaining are uncolored. There are two players — white and black. The players make moves alternatively. The white player starts the game. In his turn, a player must select one uncolored vertex and paint it in his color. The player wins if he paints some path of three vertices in his color. In case all vertices are colored and neither player won, the game ends in a draw. Could you please find who will win the game or whether it ends as a draw, assuming both players play optimally?

输入输出格式

输入格式

The first line contains a single integer $ T $ ( $ 1 \le T \le 50\,000 $ ) — the number of test cases. Then descriptions of $ T $ test cases follow. The first line of each test contains a single integer $ n $ ( $ 1 \le n \le 5 \cdot 10^5 $ ) — the number of vertices in the tree. Each of the following $ n - 1 $ lines contains integers $ v $ , $ u $ ( $ 1 \le v, u \le n $ ) denoting an edge of the tree connecting vertices $ v $ and $ u $ . The last line of a test case contains a string of letters 'W' (for white) and 'N' (for not colored) of length $ n $ denoting already colored vertices. Vertexes already colored in white are denoted as 'W'. It's guaranteed that the given edges form a tree, that there is at least one uncolored vertex and that there is no path of three white vertices. It's guaranteed that sum of all $ n $ among all test cases is at most $ 5 \cdot 10^5 $ .

输出格式

For every test case, print either "White", "Draw" or "Black", depending on the result of the game.

输入输出样例

输入样例 #1

2
4
1 2
1 3
1 4
NNNW
5
1 2
2 3
3 4
4 5
NNNNN

输出样例 #1

White
Draw

说明

In the first example, vertex $ 4 $ is already colored in white. The white player can win by coloring the vertex $ 1 $ in white first and the remaining vertex on his second turn. The process is illustrated with the pictures below. In the second example, we can show that no player can enforce their victory.