What Happens When All the Branches Fall From a Tree?

Time limit1sMemory limit1024 MB

Summary

Two players take turns removing a root-to-vertex path from a tree, and a Nim game on the removed stones decides each turn. The task is to find the winner.

Level: Hard8 of 10
Topics: Tree, Game theory, Dynamic programming, Bit manipulation
Solved: No attempts yet

문제

가지런하다 (even and tidy)

Dongwoo and Jaewoo play a game on a tree $T$ with $N$ vertices, numbered $1$ to $N$ . The root of the tree is vertex $1$ , and vertex $i$ has $C_i$ stones. The game starts with Dongwoo, and the two players take turns. A turn is defined as follows.

Let A be the player whose turn it is, and B the other player. Let $F$ be the current forest. At the start, $F=\{T\}$ .

A picks one tree in $F$ . If no tree remains, A loses.
Let $T_0$ be the chosen tree, and let $r$ be its root.
A picks a vertex $v$ in $T_0$ and takes every vertex on the path from $r$ to $v$ , including both endpoints. If $r=v$ , A takes only $r$ .
Using the taken vertices, B and A play a Nim game, starting with B. Players alternate. On each move, a player picks a vertex with at least one stone and takes any positive number of stones from it. The player who cannot move loses.
If B wins this Nim game, B immediately wins the original game.
If A wins the Nim game, A rearranges $T_0$ as follows. For each vertex directly connected to $r$ in $T_0$ , add the subtree rooted at that vertex to $F$ , except the subtree that contains $v$ . Then remove $T_0$ from $F$ .

The forest starts with one tree, but as the game goes on, it can become a collection of several trees that are not connected to each other.

A player who cannot act on their turn loses. Assuming both players play optimally, determine who wins.

Input

The first line contains the number of vertices $N$ ( $1 \le N \le 200\,000$ ).

The second line contains the stone counts $C_1, C_2, \cdots, C_N$ ( $0 \le C_i \le 10^9$ ), separated by spaces. Vertex $i$ has $C_i$ stones.

Each of the next $N-1$ lines contains two vertex numbers $P_i, Q_i$ ( $1 \le P_i, Q_i \le N$ , $P_i \ne Q_i$ ), separated by a space, that are directly connected in the tree.

The input is guaranteed to be a tree.

Output

If Dongwoo wins, print kidw0124 on the first line. If Jaewoo wins, print eoaud0108.

Hint

The title of this problem and the answer to it are the idea of kidw0124.

Examples5

Example 1
Input
```
1
0
```
Expected output
```
kidw0124
```
Example 2
Input
```
1
1
```
Expected output
```
eoaud0108
```
Example 3
Input
```
2
124 124
1 2
```
Expected output
```
kidw0124
```
Example 4
Input
```
2
124 108
1 2
```
Expected output
```
eoaud0108
```
Example 5
Input
```
4
1 1 2 2
1 2
1 3
3 4
```
Expected output
```
eoaud0108
```