{"problem":{"name":"[GDKOI2024 普及组] 捉迷藏","description":{"content":"Zayin 和 Ziyin 正在玩有趣的捉迷藏游戏。 该游戏在一颗具有 $n$ 个节点（编号从 $1$ 到 $n$）的树上进行。 在游戏的开始，Zayin 在节点 $a$，而 Ziyin 在节点 $b$。他们轮流操作，Zayin 先移动。在每次移动中，Zayin 能移动到距离当前所在点不超过 $da$ 的节点上，而 Ziyin 能移动到距离当前所在点不超过 $db$ 的节点上（注意 可以保持在","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10076"},"statements":[{"statement_type":"Markdown","content":"Zayin 和 Ziyin 正在玩有趣的捉迷藏游戏。\n\n该游戏在一颗具有 $n$ 个节点（编号从 $1$ 到 $n$）的树上进行。\n\n在游戏的开始，Zayin 在节点 $a$，而 Ziyin 在节点 $b$。他们轮流操作，Zayin 先移动。在每次移动中，Zayin\n能移动到距离当前所在点不超过 $da$ 的节点上，而 Ziyin 能移动到距离当前所在点不超过 $db$ 的节点上（注意\n可以保持在当前点不动）。\n\n当某次移动后，其中一人抓住了另外一人，即移动到了另外一人的节点上，则游戏结束，被抓住的人输掉游戏。\n\n当 Zayin 和 Ziyin 都按最优策略移动的话，谁会是最后赢家呢。\n\n注解：\n- 一颗具有 $n$ 个节点的树是指一个具有 $n$ 个节点，$n - 1$ 条边的连通无向图。\n- 树上两个节点的距离定义为连接该两点的最短路径所包含的边数。\n\n## Input\n\n每个测试点包含多个测试用例。\n\n第一行包含两个整数 $d, t$，表示测试点编号，和测试用例的数量。每个测试用例的描述如下。\n\n第一行包含两个整数 $n, q$ —— 分别为顶点数、询问数。\n\n接下来 $n-1$ 行每行包含两个整数 $u, v (1 \\leq u, v \\leq n, u \\neq v)$，表示顶点 $u$ 和 $v$ 之间具有一条直接相连的边，保证这些边形成一棵树。\n\n接下来 $q$ 行每行包含四个整数 $a, b, da, db(1 \\leq a, b, da, db \\leq n)$ 作为一次游戏，分别表示 Zayin 初始节点、Ziyin 初始节点、Zayin 最大移动距离、Ziyin 最大移动距离。\n\n## Output\n\n对于每个测试用例的每次游戏，输出一行 `Zayin` 或 `Ziyin` 表示最后赢家，特别地如果在 $10^{10^5}$ 轮内游\n戏没有仍结束，则输出 `Draw` 表示平局。\n\n[samples]\n\n## Note\n\n保证所有测试用例的 $n$ 之和不超过 $10^6$，$q$ 之和不超过 $10^6$。\n\n| 数据点编号 | $\\sum n \\leq$ | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1$ | $10$ | 无 |\n| $2$ | $100$ | $q=1$ |\n| $3$ | $100$ | 无 |\n| $4$ | $10^4$ | $q=1$ |\n| $5$ | $10^4$ | 无 |\n| $6$ | $10^6$ | $q=1$ |\n| $7,8,9,10$ | $10^6$ | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10076","tags":["2024","广东","O2优化"],"sample_group":[["1 2\n6 5\n2 3\n2 6\n2 1\n4 3\n5 1\n5 4 1 2\n6 4 4 3\n1 4 5 4\n5 2 1 4\n2 5 1 5\n4 5\n1 4\n3 4\n2 4\n4 2 2 3\n4 3 2 2\n4 3 3 3\n1 2 1 1\n1 2 1 2","Ziyin\nZayin\nZayin\nZiyin\nZiyin\nZayin\nZayin\nZayin\nDraw\nZiyin"]],"created_at":"2026-03-03 11:09:25"}}