P10076 [GDKOI2024 Junior] Hide and Seek

Zayin and Ziyin are playing an interesting game of hide and seek. The game is played on a tree with $n$ nodes (numbered from $1$ to $n$). At the start of the game, Zayin is at node $a$, and Ziyin is at node $b$. They take turns to move, with Zayin moving first. In each move, Zayin can move to any node whose distance from the current node is at most $da$, and Ziyin can move to any node whose distance from the current node is at most $db$ (note that staying at the current node is allowed). If after some move, one player catches the other, meaning they move onto the other player's node, then the game ends and the caught player loses. If both Zayin and Ziyin play with optimal strategies, who will be the final winner? Notes: - A tree with $n$ nodes means a connected undirected graph with $n$ nodes and $n - 1$ edges. - The distance between two nodes on the tree is defined as the number of edges on the shortest path connecting them.

Each test point contains multiple test cases. The first line contains two integers $d, t$, indicating the test point ID and the number of test cases. Each test case is described as follows. The first line contains two integers $n, q$, the number of vertices and the number of queries. The next $n - 1$ lines each contain two integers $u, v (1 \leq u, v \leq n, u \neq v)$, indicating that there is a directly connected edge between vertex $u$ and vertex $v$. It is guaranteed that these edges form a tree. The next $q$ lines each contain four integers $a, b, da, db(1 \leq a, b, da, db \leq n)$ describing one game, representing Zayin's starting node, Ziyin's starting node, Zayin's maximum moving distance, and Ziyin's maximum moving distance.

For each game in each test case, output one line: `Zayin` or `Ziyin`, indicating the final winner. In particular, if the game still does not end within $10^{10^5}$ rounds, output `Draw` to indicate a draw.

It is guaranteed that, over all test cases, the sum of $n$ does not exceed $10^6$, and the sum of $q$ does not exceed $10^6$. | Data Point ID | $\sum n \leq$ | Special Property | | :----------: | :----------: | :----------: | | $1$ | $10$ | None | | $2$ | $100$ | $q = 1$ | | $3$ | $100$ | None | | $4$ | $10^4$ | $q = 1$ | | $5$ | $10^4$ | None | | $6$ | $10^6$ | $q = 1$ | | $7,8,9,10$ | $10^6$ | None | Translated by ChatGPT 5