[GDKOI2024 普及组] 捉迷藏

赛事要求

2024 年广东省重点中学信息学邀请赛 (GDKOI 2024)

普及组 第二试

2024 年 1 月 7 日

注意事项

1. 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。
2. 题目测试数据有严格的时间限制，超时不得分。
3. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
4. 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。
5. 评测环境为 NOI 系列活动标准竞赛环境，编译器版本为 g++ 9.4.0。
6. 若无特殊说明，结果的比较方式为全文比较 (过滤行末空格及文末回车)。
7. 对于 C++ 选手，64 位整数输入输出格式为 %lld。
8. 选手提交的程序源文件必须不大于 100KB。
9. 对于 C++ 语言的编译选项为 -O2 -std=c++14

题目描述

Zayin 和 Ziyin 正在玩有趣的捉迷藏游戏。

该游戏在一颗具有 $n$ 个节点（编号从 $1$ 到 $n$）的树上进行。

在游戏的开始，Zayin 在节点 $a$，而 Ziyin 在节点 $b$。他们轮流操作，Zayin 先移动。在每次移动中，Zayin 能移动到距离当前所在点不超过 $da$ 的节点上，而 Ziyin 能移动到距离当前所在点不超过 $db$ 的节点上（注意 可以保持在当前点不动）。

当某次移动后，其中一人抓住了另外一人，即移动到了另外一人的节点上，则游戏结束，被抓住的人输掉游戏。

当 Zayin 和 Ziyin 都按最优策略移动的话，谁会是最后赢家呢。

注解：

• 一颗具有 $n$ 个节点的树是指一个具有 $n$ 个节点，$n - 1$ 条边的连通无向图。
• 树上两个节点的距离定义为连接该两点的最短路径所包含的边数。

输入格式

每个测试点包含多个测试用例。

第一行包含两个整数 $d, t$，表示测试点编号，和测试用例的数量。每个测试用例的描述如下。

第一行包含两个整数 $n, q$ —— 分别为顶点数、询问数。

接下来 $n-1$ 行每行包含两个整数 $u, v (1 \leq u, v \leq n, u \neq v)$，表示顶点 $u$ 和 $v$ 之间具有一条直接相连的边，保证这些边形成一棵树。

接下来 $q$ 行每行包含四个整数 $a, b, da, db(1 \leq a, b, da, db \leq n)$ 作为一次游戏，分别表示 Zayin 初始节点、Ziyin 初始节点、Zayin 最大移动距离、Ziyin 最大移动距离。

输出格式

对于每个测试用例的每次游戏，输出一行 Zayin 或 Ziyin 表示最后赢家，特别地如果在 $10^{10^5}$ 轮内游 戏没有仍结束，则输出 Draw 表示平局。

样例 #1

样例输入 #1

1 2
6 5
2 3
2 6
2 1
4 3
5 1
5 4 1 2
6 4 4 3
1 4 5 4
5 2 1 4
2 5 1 5
4 5
1 4
3 4
2 4
4 2 2 3
4 3 2 2
4 3 3 3
1 2 1 1
1 2 1 2

样例输出 #1

Ziyin
Zayin
Zayin
Ziyin
Ziyin
Zayin
Zayin
Zayin
Draw
Ziyin

提示

保证所有测试用例的 $n$ 之和不超过 $10^6$，$q$ 之和不超过 $10^6$。

数据点编号	$\sum n \leq$	特殊性质
$1$	$10$	无
$2$	$100$	$q=1$
$3$		无
$4$	$10^4$	$q=1$
$5$		无
$6$	$10^6$	$q=1$
$7,8,9,10$		无