CF1110G.Tree-Tac-Toe

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?

井字棋游戏将在一棵包含 $n$ 个顶点的树上进行。其中一些顶点已被染成白色，其余顶点尚未染色。

游戏有两个玩家：白方和黑方。双方轮流行动，白方先手。在自己的回合中，玩家必须选择一个未染色的顶点，并将其染成自己的颜色。

若某位玩家成功将某条长度为三的路径上的所有三个顶点都染成自己的颜色，则该玩家获胜。若所有顶点均被染色后仍无玩家获胜，则游戏以平局结束。

假设双方均采取最优策略，请判断哪位玩家将获胜，或游戏是否将以平局结束。

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$.

第一行包含一个整数 $T$（$1 \le T \le 50\,000$），表示测试用例的数量。随后是 $T$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$），表示树中顶点的数量。

接下来的 $n - 1$ 行每行包含两个整数 $v$、$u$（$1 \le v, u \le n$），表示树中连接顶点 $v$ 和 $u$ 的一条边。

测试用例的最后一行是一个长度为 $n$ 的字符串，由字符 'W'（表示白色）和 'N'（表示未着色）组成，用于表示已着色的顶点。已被着色为白色的顶点用 'W' 表示。

保证所给边构成一棵树，至少存在一个未着色顶点，且不存在长度为三的全白顶点路径。

保证所有测试用例的 $n$ 值之和不超过 $5 \cdot 10^5$。

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

对于每个测试用例，根据游戏结果输出“White”、“Draw”或“Black”。

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.

在第一个例子中，顶点 $4$ 已被染成白色。白方玩家可以通过第一步将顶点 $1$ 染成白色，第二步再将剩余的顶点染成白色来获胜。该过程如下图所示。

在第二个例子中，可以证明双方均无法强制获胜。