https://codeforces.com/contest/1405/problem/D
題意：在一棵頂點為n的樹上，Alice和Bob開始位于兩個不同的頂點，輪流移動，Alice先手，移動時允許停留在同一個頂點上，如果無限步內Alice和Bob占據了同一個頂點，Alice勝，否則Bob勝，求勝者，
思路：考慮YES/NO的單方面，
考慮YES，根據樣例，如果Alice能第一步抓到Bob，直接win，所以判Alice和Bob的dis是否<=da，直接用向上標記法求也可以，不必lca，
然后看到第二個鏈子，想到如果在樹的直徑的中點，Alice的跨越距離能到樹直徑兩端，那么整個樹都能被抓到，Alice必贏，判一個fardis<=da*2，
然后第三個有一點難想， 比如Bob在Alice的da*2的多一個點上，這時候Bob想要逃出去肯定要能每次跳出這個范圍，跳出的條件是db>da*2，所以第三個條件是da*2>=db,Alicewin，
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
bool vis[maxn];
vector<LL>g[maxn];
LL n,a,b,da,db;
LL dis=0,fardis=0,farnode=0;
void init()
{
for(LL i=0;i<=n+10;i++) vis[i]=0;
dis=0;fardis=0;farnode=0;
}
void dfs1(LL u,LL fa,LL end,LL step)//求a和b的距離
{
vis[u]=1;
if(u==end)
{
dis=step;
return;
}
for(LL i=0;i<g[u].size();i++)
{
LL v=g[u][i];
if(vis[v]||v==fa) continue;
vis[v]=1;
dfs1(v,u,end,step+1);
}
}
void dfs2(LL u,LL fa,LL step)//求樹的直徑
{
vis[u]=1;
for(LL i=0;i<g[u].size();i++)
{
LL v=g[u][i];
if(vis[v]||v==fa) continue;
vis[v]=1;
dfs2(v,u,step+1);
}
if(step>fardis){
fardis=step;
farnode=u;
}
}
void solve()
{
cin>>n>>a>>b>>da>>db;init();
for(LL i=0;i<=n+10;i++) g[i].clear();
for(LL i=1;i<n;i++)
{
LL x,y;cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(a,-1,b,0);//條件一
if(dis<=da){
cout<<"Alice"<<endl;return;
}
init();
dfs2(1,-1,0);//條件二:求樹直徑
for(LL i=0;i<=n+10;i++) vis[i]=0;
dfs2(farnode,-1,0);
//debug(fardis);
if(fardis<=da*2){
cout<<"Alice"<<endl;return;
}
if(db<=da*2){
cout<<"Alice"<<endl;return;
}
cout<<"Bob"<<endl;return;
}
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
LL t;cin>>t;
while(t--)
{
solve();
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/1484.html
標籤：區塊鏈