나무에서 나뭇가지가 다 사라지면?

가지런하다

동우와 재우가 $N$개의 정점으로 이루어진 트리 $T$에서 게임을 한다. 정점은 $1$번부터 $N$번까지 번호가 붙어 있고, 트리의 루트는 $1$번 정점이다. $i$번 정점에는 $C_i$개의 돌이 있다. 게임은 동우부터 시작해 두 사람이 턴을 번갈아 진행한다. 한 턴은 다음과 같이 진행한다.

현재 턴을 진행하는 사람을 A, 다른 사람을 B라 하자. 현재 상태의 포레스트를 $F$라 하며, 처음에는 $F=\{T\}$이다.

1. A는 $F$에 포함된 트리 하나를 고른다. 남은 트리가 없다면 A가 진다.
2. A가 고른 트리를 $T_0$라 하고, 그 루트 정점을 $r$이라 하자.
3. A는 $T_0$에서 정점 $v$를 하나 고른다. $r$에서 $v$까지 경로 위의 모든 정점을 양 끝점을 포함해 가져온다. $r=v$이면 $r$만 가져온다.
4. 가져온 정점들로 B부터 시작하는 님 게임을 한다. 두 사람은 번갈아 행동한다. 각 행동에서는 돌이 1개 이상 있는 정점을 하나 골라 원하는 만큼 돌을 가져간다. 더 이상 행동하지 못하는 사람이 진다.
5. 이 님 게임에서 B가 이기면, 원래 게임도 즉시 B가 이긴다.
6. 님 게임에서 A가 이겼다면, $T_0$를 다음과 같이 재배치한다. $T_0$에서 $r$과 직접 연결된 정점마다 그 정점을 루트로 하는 서브트리를 $F$에 추가한다. 단, $v$를 포함하는 서브트리는 추가하지 않는다. 그 뒤 $T_0$를 $F$에서 제거한다.

처음 포레스트에는 트리가 하나뿐이지만, 게임이 진행되면서 서로 연결되지 않은 여러 트리로 이루어진 포레스트가 될 수 있다.

자신의 턴에 행동할 수 없는 플레이어가 패배한다. 두 사람이 최적으로 게임을 진행할 때 누가 이기는지 판단하라.

첫째 줄에 트리의 정점 개수 $N$ ($1 \le N \le 200\,000$)이 주어진다.

둘째 줄에 각 정점에 놓인 돌의 개수 $C_1, C_2, \cdots, C_N$ ($0 \le C_i \le 10^9$)이 공백으로 구분되어 주어진다. $i$번 정점에 $C_i$개의 돌이 있다는 뜻이다.

셋째 줄부터 $N-1$개의 줄에 걸쳐 트리에서 직접 연결된 두 정점 번호 $P_i, Q_i$ ($1 \le P_i, Q_i \le N$, $P_i \ne Q_i$)가 공백으로 구분되어 주어진다.

주어지는 입력은 항상 트리이다.

동우가 이기면 첫째 줄에 kidw0124를, 재우가 이기면 eoaud0108을 출력한다.

이 문제의 제목과 제목에 대한 답은 kidw0124의 아이디어이다.