P10076 [GDKOI2024 普及组] 捉迷藏 题解

· · 题解

学校模拟赛 vp 了普及组第二天，喜提 100+60+85+16=261，可惜没去现场。

题意简述

给定一棵树，再给出树上两点的位置。两点交替移动，第一个点每次可以移动 [0, da] 步，第二个点每次可以移动 [0, db] 步。

当一个点移动到另一个点的位置上时，该点获胜。

问哪个点会获胜，或告知平局。

思路

我们分情况讨论。

下文 dist 表示两点的距离。

开始时第一个点就能移动到第二个点的位置上

那么就说明 dis \le da，倍增 LCA 求解两点距离即可。

这种情况肯定是第一个点获胜。

da = db

显然，当第一个点移动到再移动一次就能满足 dis \le da 的位置时，此时必然也满足 dis \le db。

而且，第一个点移动之后，就轮到第二个点移动了，因为 dis \le db。所以第二个点就可以直接移动到当前第一个点的位置。第一个点肯定不希望这种事情发生。

所以两个点永远都不会让 dis \le da 满足，肯定是平局。

da > db

那么就肯定存在满足第一个点移动后，db < dis \le da 的情况。

此时第二个点无法移动到第一个点，而且若不移动到第一个点的移动范围外，再轮到第一个点移动时，就会让第一个点移动到自己的位置上。

所以第二个点就只能躲避第一个点。

但是树上不存在环，躲到最后肯定会无路可逃，所以这种情况肯定是第一个点赢。

db > da

由上个情况同理可证：这种情况肯定是第二个点赢。

Code

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000005;
struct Edge{
    int to, nxt;
}g[N << 1];
int h[N], idx;
int dep[N], f[N][18];
void add(int a,int b)
{
    g[++idx].to = b, g[idx].nxt = h[a], h[a] = idx;
}
void dfs(int u,int fa)
{
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (j == fa)
            continue;
        dep[j] = dep[u] + 1;
        f[j][0] = u;
        for (int k=1;k<18;k++)
            f[j][k] = f[f[j][k - 1]][k - 1];
        dfs(j, u);
    }
}
int lca(int a,int b)
{
    if (dep[a] < dep[b])
        swap(a, b);
    for (int i=17;i>=0;i--)
        if (dep[f[a][i]] >= dep[b])
            a = f[a][i];
    if (a == b)
        return a;
    for (int i=17;i>=0;i--)
        if (f[a][i] != f[b][i])
        {
            a = f[a][i];
            b = f[b][i];
        }
    return f[a][0];
}
inline int dist(int a,int b)
{
    return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
int main()
{
    int T;
    scanf("%*d%d", &T);
    while (T--)
    {
        int n, q;
        scanf("%d%d", &n, &q);
        for (int i=1;i<=n;i++)
            h[i] = 0;
        idx = 0;
        for (int i=1;i<n;i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);
        }
        dfs(1, 1);
        while (q--)
        {
            int a, b, da, db;
            scanf("%d%d%d%d", &a, &b, &da, &db);
            if (dist(a, b) <= da)
                puts("Zayin");
            else if (da == db)
                puts("Draw");
            else if (da > db)
                puts("Zayin");
            else
                puts("Ziyin");
        }
    }
    return 0;
}