[GDKOI2024 普及组] 捉迷藏

yzx3195 · 2024-01-21 16:52:10 · 题解

题目大意

Zayin 和 Ziyin 在一颗树上互追，谁先移动到另外一个人所在的结点上就算胜利，两个人都会按照最优方式移动，询问最后谁会赢。若在 10^{10^5} 后，仍没人抓得到对方，则输出平手 Draw。

做法

显然，树上求两点之间的距离，用 LCA，下面给出公式：dis_{a,b} = depth_a + depth_b - 2 \times depth_{lca} , 其中，depth_x 表示结点 x 的深度，lca 表示 a, b 两点的最近公共祖先。

想必大家都会求 LCA 吧。

对于 Zayin，只要当前 Zayin 可移动的距离 da 大于了 Zayin 与 Ziyin 之间的距离，那么 Zayin 就可以抓住 Ziyin，或者，Zayin 可移动的距离 da 大于 Ziyin 可移动的距离 db。这样，在若干次操作之后，Ziyin 一定会被 Zayin 逼到树上的某一个点上，所以 Zayin 在这种情况下也会胜利。

对于 Ziyin 也同理。

当且仅当 da = db 时，两人平手。

时间复杂度为 O(T(n \log n + q \log n))，卡一卡常也能通过本题。

切记，清零不要用 memset，否则会 TLE。

Code

#include<bits/stdc++.h>
using namespace std;

#define re register

const int MAXN = 1e06 + 7;

const int LG = 20;

int d, t;

int n, q;

int lg;

struct Edge {
    int to;
    int nxt;
} Num[MAXN * 2];//双向边开两倍

int head[MAXN * 2];

int cnt;

int f[MAXN][LG];

int depth[MAXN];

void add(int x, int y)
{
    Num[++cnt].to = y;
    Num[cnt].nxt = head[x];
    head[x] = cnt;
    return ;
}

void dfs(int x, int fa)//LCA预处理
{
    f[x][0] = fa, depth[x] = depth[fa] + 1;
    for(re int i = 1; (1 << i) <= depth[x]; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for(re int i = head[x]; i; i = Num[i].nxt)
    {
        if(Num[i].to != fa)
        {
            dfs(Num[i].to, x);
        }
    }
    return;
}

int LCA(int x, int y)//倍增求LCA
{
    if(x == y)
        return x;
    if(depth[x] < depth[y])
        swap(x, y);
    for(re int i = lg; i >= 0; i--)
    {
        if(depth[x] - (1 << i) >= depth[y])
            x = f[x][i];
    }
    if(x == y)
        return x;
    for(re int i = lg; i >= 0; i--)
    {
        if(f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}

inline void read(int &x)//卡常小技巧
{
    int f = 1;
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f *= -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    x *= f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-'), x = -x;
    }
    if (x > 9)
    {
        write(x / 10);
    }
    putchar(x % 10 ^ 48);
}

signed main()
{
//  freopen("game.in", "r", stdin);
//  freopen("game.out", "w", stdout);
    read(d), read(t);

    while(t--)
    {
        read(n), read(q);
        lg = log2(n);
        cnt = 0;
        for(re int i = 1; i <= n; i++)//不要用 memset!
        {
            depth[i] = 0, Num[i].nxt = 0, Num[i].to = 0, head[i] = 0;
            for(re int j = 1; j <= lg; j++)
            {
                f[i][j] = 0;
            }
        }
        for(re int i = 1; i < n; i++)
        {
            int u, v;
            read(u), read(v);
            add(u, v), add(v, u);
        }
        dfs(1, 0);
        int a, b, da, db;
        for(re int i = 1; i <= q; i++)
        {
            read(a), read(b), read(da), read(db);
            int dis = depth[a] + depth[b] - 2 * (depth[LCA(a, b)]);
            if(dis <= da)
            {
                putchar('Z'), putchar('a'), putchar('y'), putchar('i'), putchar('n');
                putchar('\n');
            }
            else if(da > db)
            {
                putchar('Z'), putchar('a'), putchar('y'), putchar('i'), putchar('n');
                putchar('\n');
            }
            else if(da == db)
            {
                putchar('D'), putchar('r'), putchar('a'), putchar('w');
                putchar('\n');
            }
            else
            {
                putchar('Z'), putchar('i'), putchar('y'), putchar('i'), putchar('n');
                putchar('\n');
            }
        }
    }

}