4728: 捉迷藏(广东省重点中学信息学邀请赛普及组)
内存限制：512 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
（广东省重点中学信息学邀请赛 (GDKOI 2024 day2普及组 第二试)
Zayin和Ziyin正在玩有趣的捉迷藏游戏。
该游戏在一颗具有n个节点（编号从1到n）的树上进行。
在游戏的开始，Zayin在节点a，而Ziyin在节点b。他们轮流操作，Zayin先移动。在每次移动中，Zayin能移动到距离当前所在点不超过da的节点上，而Ziyin能移动到距离当前所在点不超过db的节点上（注意 可以保持在当前点不动）。
当某次移动后， 其中一人抓住了另外一人， 即移动到了另外一人的节点上， 则游戏结束， 被抓住的人输 掉游戏。
当Zayin和Ziyin都按最优策略移动的话，谁会是最后赢家呢。
注解：
• 一颗具有n个节点的树是指一个具有n个节点，n−1条边的连通无向图。
• 树上两个节点的距离定义为连接该两点的最短路径所包含的边数。
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≤u, v≤n,u≠v)，表示顶点u和v之间具有一条直接相连的边，保证这些边形成一棵树。
接下来q行每行包含四个整数a,b, da, db(1≤a,b, da, db≤n) 作为一次游戏， 分别表示Zayin初始节点、Ziyin初始节点、Zayin最大移动距离、Ziyin最大移动距离。
第一行包含两个整数d, t，表示测试点编号，和测试用例的数量。每个测试用例的描述如下。
第一行包含两个整数n, q — 分别为顶点数、询问数。
接下来n−1 行每行包含两个整数u, v(1≤u, v≤n,u≠v)，表示顶点u和v之间具有一条直接相连的边，保证这些边形成一棵树。
接下来q行每行包含四个整数a,b, da, db(1≤a,b, da, db≤n) 作为一次游戏， 分别表示Zayin初始节点、Ziyin初始节点、Zayin最大移动距离、Ziyin最大移动距离。
输出
对于每个测试用例的每次游戏， 输出一行”Zayin” 或”Ziyin” 表示最后赢家， 特别地如果在 
轮内游 戏没有仍结束，则输出”Draw” 表示平局。
轮内游 戏没有仍结束，则输出”Draw” 表示平局。样例输入 复制
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样例输出 复制
Ziyin
Zayin
Zayin
Ziyin
Ziyin
Zayin
Zayin
Zayin
Draw
Ziyin提示
数据范围：
保证所有测试用例的 n 之和不超过 106 ，q 之和不超过 106。
保证所有测试用例的 n 之和不超过 106 ，q 之和不超过 106。
|
数据点编号
|
∑ n ≤
|
特殊性质
|
|
1
|
10
|
无
|
|
2
|
100
|
q=1
|
|
3
|
100
|
无
|
|
4
|
104
|
q=1
|
|
5
|
104
|
无
|
|
6
|
106
|
q=1
|
|
7,8,9,10
|
106
|
无
|