Codeforces Round 668 (Div. 2) D. Tree Tag

Link: Codeforces Round 668 (Div. 2) D. Tree Tag

Description

点击查看题面

Alice and Bob are playing a fun game of tree tag.

The game is played on a tree of n vertices numbered from 1 to n. Recall that a tree on n vertices is an undirected, connected graph with n−1 edges.

Initially, Alice is located at vertex a, and Bob at vertex b. They take turns alternately, and Alice makes the first move. In a move, Alice can jump to a vertex with distance at most da from the current vertex. And in a move, Bob can jump to a vertex with distance at most db from the current vertex. The distance between two vertices is defined as the number of edges on the unique simple path between them. In particular, either player is allowed to stay at the same vertex in a move. Note that when performing a move, a player only occupies the starting and ending vertices of their move, not the vertices between them.

If after at most moves, Alice and Bob occupy the same vertex, then Alice is declared the winner. Otherwise, Bob wins.

Determine the winner if both players play optimally.

输入描述:

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1e4). Description of the test cases follows.

The first line of each test case contains five integers n,a,b,da,db (2≤n≤1e5, 1≤a,b≤n, a≠b, 1≤da,db≤n−1) — the number of vertices, Alice's vertex, Bob's vertex, Alice's maximum jumping distance, and Bob's maximum jumping distance, respectively.

The following n−1 lines describe the edges of the tree. The i-th of these lines contains two integers u, v (1≤u,v≤n,u≠v), denoting an edge between vertices u and v. It is guaranteed that these edges form a tree structure.

It is guaranteed that the sum of n across all test cases does not exceed 1e5.

输出描述:

For each test case, output a single line containing the winner of the game: "Alice" or "Bob".

input
4
4 3 2 1 2
1 2
1 3
1 4
6 6 1 2 5
1 2
6 5
2 3
3 4
4 5
9 3 9 2 5
1 2
1 6
1 9
1 3
9 5
7 9
4 8
4 3
11 8 11 3 3
1 2
11 9
4 9
6 5
2 10
3 2
5 9
8 3
7 4
7 10
output
Alice
Bob
Alice
Alice

Probelm solving

这道题的意思就是给你一个无向连通图，给定两个人的初始位置以及每次最多可以前进的距离(只要距离小于这个都可以走)，问你第一个人(Alice)是否追得上第二个人(Bob),追得上的话输出Alice，否则输出Bob。

搜的是dp的tag的题，没想到遇到一个博弈论的问题（反正自己是一点思路都没有。大概看了下题解才知道怎么写了。

我们首先考虑必胜态，什么情况下一定追得上呢，就是以下这三种

  1. Alice每次可以移动的最大距离大于两个人的初始距离，直接冲着Bob去就追上了
  2. Alice每次可以移动的最大距离大于图中最远的两个点之间的距离的一半，也就是说Alice先跑到图的中间，任你Bob往哪去，下次Alice可以到达任何一个点，所以肯定可以捉到Bob
  3. Alice每次可以移动的最大距离大于Bob每次可移动的最大距离的一半，因为两个人都是最优的走法，Alice是对着Bob的方向走，Bob肯定会想着远离Alice，但是如果他走到边界，Alice会越来越近，如果此时Alice每次可以移动的最大距离大于Bob每次可移动的最大距离的一半，即使Bob抓紧时间往回跑，也一定会被Alice抓到

所以我们只需要考虑这三种情况就行了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
const int maxn = 1e5+10;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
int d[4][2]={1,0,0,1,-1,0,0,-1};
int n,a,b,da,db,pos,head[maxn],dis[maxn];
struct node{
    int to,nxt;
}p[maxn<<1];
void add(int from,int to){
    p[pos].nxt=head[from];
    p[pos].to=to;
    head[from]=pos++;
}
void dfs(int now,int from){
    for(int i=head[now];i!=-1;i=p[i].nxt){
        if(p[i].to==from)    continue;
        dis[p[i].to]=dis[now]+1;
        dfs(p[i].to,now);
    }
}
int main() {
    ios::sync_with_stdio(0);
    #ifdef Uncle_drew
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #else
    #endif
    int t;
    cin>>t;
    while(t--){
        cin>>n>>a>>b>>da>>db;
        pos=0;
        for(int i=1;i<=n;i++)    dis[i]=0,head[i]=-1;
        for(int i=1,x,y;i<n;i++){
            cin>>x>>y;
            add(x,y);add(y,x);
        }
        dfs(1,0);
        int ma=0,root=1;
        for(int i=1;i<=n;i++){
            if(dis[i]>ma){
                ma=dis[i];
                root=i;
            }
        }
        for(int i=1;i<=n;i++)    dis[i]=0;
        ma=0;
        dfs(root,0);
        for(int i=1;i<=n;i++){
            ma=max(ma,dis[i]);
        }
        for(int i=1;i<=n;i++)    dis[i]=0;
        dfs(a,0);
        if(da>=dis[b]||da*2>=ma||da*2>=db)    cout<<"Alice\n";
        else cout<<"Bob\n";
    }
    return 0;
}
赏