Tree-Tac-Toe
Contest: Codeforces Global Round 1
Difficulty rating: 3100
Tags: constructive algorithms, games, trees

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?

Input format:
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$$$.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
2
4
1 2
1 3
1 4
NNNW
5
1 2
2 3
3 4
4 5
NNNNN

Example output:
White
Draw

Editorial:
To start with, let's notice that the white vertices are not necessary. Actually, you can solve the problem analyzing the cases with the whites as well, but there is an easy way to get rid of them:
Examine the following construction:
That is, replace the white $$$A$$$ with some set of four non-white vertices.
One can notice, that neither white nor black can win on these four vertices. That means that they are actually interested in getting the color of the end of this graph, connected to the remaining graph being of their color — it can help them later.
Let's start the game as white player and paint a vertex $$$A$$$ white. If black player will not paint the vertex $$$B$$$ black, we have a win. Otherwise, two turns have passed now and that means that the "parity" has preserved and it is our turn again. Then we can play as we would have played in the original game, except if the black player paints $$$C$$$ or $$$D$$$ in some point, we should color the remaining one (and the parity will preserve again).
———————
Now let's solve the problem assuming there are no white vertices.
Note, that if there is a vertex of degree $$$4$$$ or more, then the white player wins, maing the first move into that vertex, and then two moves in some leaves of this vertex.
In case there is a vertex of degree $$$3$$$ having at least two non-white neighbors, then it's a win as well: we can either collect a path going through this vertex or going through non-leave neighbor somewhere else.
Now, note that if there are at least $$$3$$$ vertexes of degree $$$3$$$, this implies the case above.
So we are left with a case when there are at most three vertices of degree $$$3$$$ and all other have degree $$$1$$$ or $$$2$$$.
It's natural to claim (and many got wa2 for that), that all remaining cases are draws. But it's not true:
It's easy to see, that this game (picture above) is winning for white. Applying the same argument, as before, we can deduce that the game above is equivalent to the game below. Which is clearly winning for white.
Actually, any path having odd number of vertices and colored in white on both ends is winning for white (make a move into the vertex colored blue on the picture below):
This actually meains, that in our solution, in which we got rid of all white vertices, the winning cases are «bones» having odd number of vertices.
It's possible to show, that in all other cases the game will end in draw.