战争游戏

watersail / 2024-08-11 / 原文

当我们考虑树的直径时，我们不应该孤立地考察这条链，而应考虑这条链在整棵树中的地位
也就是说，如果树的直径不超过2*r1,进攻方选择树的直径的中点即可覆盖整棵树的节点
尝试证明你感受到的结论，而不是逃避它；相信OI是美的
在经过树的直径判定后，进攻方选择任意一个节点都不可能覆盖树的全部节点，这样只要2*r1<r2，防守方一定可以躲避成功
反过来，如果2r1>=r2,进攻方一定可以把防守方逼入“死角”，只要选择距离为r1的点即可；为什么一定存在这样的点呢？反证法，假设不存在这样的点，不妨设s为根考虑，树的直径就小于2r1

点击查看代码

#include <bits/stdc++.h>
using namespace std;
vector<int>a[100005];
int f[100005],g[100005],ans;
void dp(int n1,int fa)
{
	f[n1]=g[n1]=0;
	for(int i=0;i<a[n1].size();i++)
	{
		if(a[n1][i]!=fa)
		{
			dp(a[n1][i],n1);
			g[n1]=max(g[n1],f[n1]+f[a[n1][i]]+1);
			f[n1]=max(f[a[n1][i]]+1,f[n1]);
		}
	}
	ans=max(ans,g[n1]);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n,s,r1,r2;
		cin>>n>>s>>r1>>r2;
		for(int i=1;i<=n;i++)
		{
			a[i].clear();
		}
		for(int i=1;i<n;i++)
		{
			int u,v;
			cin>>u>>v;
			a[u].push_back(v);
			a[v].push_back(u); 
		}
		ans=0;
		dp(1,0);
		if(2*r1>=ans)
		{
			cout<<"Kangaroo_Splay"<<endl;
		}
		else if(2*r1>=r2)
		{
			cout<<"Kangaroo_Splay"<<endl;
		}
		else
		{
			cout<<"General_Kangaroo"<<endl;
		}
	}
	return 0;
}