[GDKOI2024 普及组] 捉迷藏

Luogu
IDLGP10076
Time3000ms
Memory512MB
DifficultyP3
2024广东O2优化
Zayin 和 Ziyin 正在玩有趣的捉迷藏游戏。 该游戏在一颗具有 $n$ 个节点(编号从 $1$ 到 $n$)的树上进行。 在游戏的开始,Zayin 在节点 $a$,而 Ziyin 在节点 $b$。他们轮流操作,Zayin 先移动。在每次移动中,Zayin 能移动到距离当前所在点不超过 $da$ 的节点上,而 Ziyin 能移动到距离当前所在点不超过 $db$ 的节点上(注意 可以保持在当前点不动)。 当某次移动后,其中一人抓住了另外一人,即移动到了另外一人的节点上,则游戏结束,被抓住的人输掉游戏。 当 Zayin 和 Ziyin 都按最优策略移动的话,谁会是最后赢家呢。 注解: - 一颗具有 $n$ 个节点的树是指一个具有 $n$ 个节点,$n - 1$ 条边的连通无向图。 - 树上两个节点的距离定义为连接该两点的最短路径所包含的边数。 ## Input 每个测试点包含多个测试用例。 第一行包含两个整数 $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 最大移动距离。 ## Output 对于每个测试用例的每次游戏,输出一行 `Zayin` 或 `Ziyin` 表示最后赢家,特别地如果在 $10^{10^5}$ 轮内游 戏没有仍结束,则输出 `Draw` 表示平局。 [samples] ## Note 保证所有测试用例的 $n$ 之和不超过 $10^6$,$q$ 之和不超过 $10^6$。 | 数据点编号 | $\sum n \leq$ | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $10$ | 无 | | $2$ | $100$ | $q=1$ | | $3$ | $100$ | 无 | | $4$ | $10^4$ | $q=1$ | | $5$ | $10^4$ | 无 | | $6$ | $10^6$ | $q=1$ | | $7,8,9,10$ | $10^6$ | 无 |
Samples
Input #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
Output #1
Ziyin
Zayin
Zayin
Ziyin
Ziyin
Zayin
Zayin
Zayin
Draw
Ziyin
API Response (JSON)
{
  "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可以保持在...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments