Codeforces Round #668 (Div. 2) D. Tree Tag 题解(博弈)

题目链接

题目大意

给你一颗树，Alice在a点，Bob在b点，Alice最多走da步，Bob最多走db步，两人轮流走路。要你判断经过无数次追赶后，Alice是否可以追上Bob，两人进行的都是最优策略

题目思路

感觉也不特别像一个博弈，但是也不知道该划分到哪里了

这个题目没想象的那么难，首先如果a和b的距离小于da，那么肯定Alice胜，如果2da>=len,len代表树的直径，那么也是Alice胜。 前两个都是显然的。 还有一种如果2*da>=db,这个代表不存在A只差一步追上B的时候，B可以反向再跑一段很长的距离，使得A一步追不上B。那么也是Alice胜

代码

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define fi first
#define se second
#define debug printf(" I am here\n");
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-10;
int n,a,b,da,db,dis[maxn];
int head[maxn],cnt;
struct node{
int to,next;
}e[maxn<<1];
void add(int u,int v){
e[++cnt]={v,head[u]};
head[u]=cnt;
}
void dfs(int son,int fa){
int cur=0;
for(int i=head[son];i;i=e[i].next){
if(e[i].to==fa) continue;
dis[e[i].to]=dis[son]+1;
dfs(e[i].to,son);
}
}
void init(){
cnt=0;
for(int i=1;i<=n;i++){
head[i]=dis[i]=0;
}
}
signed main(){
int _; scanf("%d", &_);
while(_--){
scanf("%d%d%d%d%d",&n,&a,&b,&da,&db);
init();
for(int i=1,u,v;i<=n-1;i++){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs(a,-1);
bool flag=0;
if(da>=dis[b]){//第一次直接抓住Bob
flag=1;
}
int ma=0,v;
for(int i=1;i<=n;i++){//寻找最远的端点
if(dis[i]>ma){
ma=dis[i];
v=i;
}
}
for(int i=1;i<=n;i++){
dis[i]=0;
}
dfs(v,-1);
int len=0;
for(int i=1;i<=n;i++){
len=max(len,dis[i]);
//树的直径
}
if(2*da>=len||2*da>=db){
flag=1;
}
puts(flag?"Alice":"Bob");
}
return 0;
}