【Codeforces1404B】Tree tag | 树上追击、博弈、树的直径

题目链接：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