自动搬运

查看原文

来自洛谷，原作者为

	yzx3195 To my mediocre OI life.

搬运于2025-08-24 22:54:26，当前版本为作者最后更新于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');
			}
		}
	}
	
}