CF #668 (Div. 2)部分

漏打发现很亏

D.Tree Tag

题意：

现在有一棵树，有两个人$A,B$在树上做游戏，$A,B$初始分别在$a,b$节点上，$A$每次最多可以跳到离自己距离为$da$的节点上，$B$每次最多可以跳到离自己距离为$db$的节点上，每回合可以选择跳或不跳，$A$先行动，可操作无数次，若$A,B$能到同一个节点上则$A$赢，否则$B$赢。

题解：

我们考虑以下几种情况：

$Case\ 1: da\ge dist(a,b)$

这种情况下无论如何$A$先行动，$A$肯定赢。

$Case\ 2:2\times da\ge D_{tree}$（树的直径）

这种情况下，$A$第一步只需要移动到树的重心位置，下一步哪里都能到，$A$赢。

$Case\ 3:2\times da\ \ \ db$

将这棵树看成以$a$为根的树，则$b$是在$a$的子树内的一个结点，当逼近到可以抓到$B$的时候，有两种情况，一是$2\times da\ge db$,这种情况下，无论$B$，怎么走，两回合内$A$必定能抓到$B$；二是$2\times da < db$，这种情况下$A,B$无限接近，但就是抓不到。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define EB emplace_back
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _sfor(p,st) for(auto &p:st)
#define endl '\n'
using namespace std;
typedef long long ll;


int dep[100005];
int D,t;
vector<int>e[100005];
void dfs(int u,int f,int d){
  dep[u]=d;
  if(dep[u]>D)t=u,D=dep[u];
  _sfor(v,e[u]){
    if(v!=f)dfs(v,u,d+1);
  }
}
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    int n;cin>>n;
    int a,b,da,db;cin>>a>>b>>da>>db;
    _for(i,1,n+1)e[i].clear();
    int u,v;
    _for(i,1,n){
      cin>>u>>v;
      e[u].EB(v),e[v].EB(u);
    }
    D=0;
    dfs(a,0,0);
    int dab=dep[b];
    dfs(t,0,0);
    if(dab<=da||2*da>=min(D,db))cout<<"Alice\n";
    else cout<<"Bob\n";
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/09/24/CF-668-Div-2-部分/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！