欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

【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