标签：战争 进攻方 游戏 r2 int 100005 ans r1
- 当我们考虑树的直径时，我们不应该孤立地考察这条链，而应考虑这条链在整棵树中的地位
- 也就是说，如果树的直径不超过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;
}
标签：战争,
进攻方,
游戏,
r2,
int,
100005,
ans,
r1
From： https://www.cnblogs.com/watersail/p/18353680