【Codeforces1404B】Tree tag | 树上追击、博弈、树的直径
程序员文章站
2022-03-27 15:56:44
题目链接:https://codeforces.com/contest/1404/problem/B题目大意:Aiice和Bob在一棵树上,初始Alice在a点 , Bob在b点,Alice可以一次走da步,Bob可以一次走db步,Alices先走,询问Alices是否能追上Bob题目思路:首先很明确的一点:如果从Alices为根的树,Bob的深度小于等于da那么Alice必赢其次考虑如果da*2 >= mx(树的直径),那么就表明Alice走完第一步之后就可以到达任何点,所以...
题目链接:https://codeforces.com/contest/1404/problem/B
题目大意:
Aiice和Bob在一棵树上,初始Alice在a点 , Bob在b点,Alice可以一次走da步,Bob可以一次走db步,Alices先走,询问Alices是否能追上Bob
题目思路:
首先很明确的一点:
如果从Alices为根的树,Bob的深度小于等于da那么Alice必赢
其次考虑如果da*2 >= mx(树的直径),那么就表明Alice走完第一步之后就可以到达任何点,所以此时Alice也必赢
所以就考虑da与db的关系了
如果2*da >= db:
因为Alice先走,所以此时Alice肯定会把Bob逼到一个死胡同里,因为此时db小于等于2*da,所以Bob只能逃跑,而不能迎面冲锋
如果2*da < db:
那么此时Bob就可以变聪明了,因为第一次到达不了Bob,所以说当Alice距离Bob小于da时,Bob就可以反向走,跳到另一边,因为此时db > 2*da 所以现在距离还是大于da,所以Bob可以一直绕圈子!
Code:
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF= 1e16;
const int maxn = 1e6+7;
const int mod= 998244353;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll a,b,da,db;
ll s[maxn],t[maxn];
vector<int>v[maxn];
int deep[maxn];
ll ans = 0;
ll dfs(int u,int fa){
ll res=1;
ll maxl=0;
deep[u] = deep[fa] + 1;
for(int e:v[u]){
if(e==fa) continue;
ll temp=dfs(e,u);
ans=max(ans,temp+maxl+1);
maxl=max(maxl,temp);
res=maxl+1;
ans=max(res,ans);
}
return res;
}
int main()
{
int T;scanf("%d",&T);
while(T--){
read(n);read(a);read(b);read(da);read(db);
for(int i=1;i<=n;i++) v[i].clear();
for(int i=1;i<=n-1;i++){
int x,y;scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
ans = 0;
deep[a] = -1;
dfs(a,a);
ans--;
if(deep[b]<=da) printf("Alice\n");
else if(2*da>=ans) printf("Alice\n");
else if(2*da>=db) printf("Alice\n");
else printf("Bob\n");
}
return 0;
}/***
2
7 4 4
ABCFBFF
1 2
2 3
6 5
4 5
5 F
7 B
6 B
1 B
***/
本文地址:https://blog.csdn.net/qq_43857314/article/details/109266637