D. Tree Tag
一、題目大意
給你一棵有n個節點的無向樹，兩個人Alice和Bob一開始分別在a，b兩個節點，Alice一次最多移動da個位置，Bob一次最多移動db個位置，當Alice在某次回合中移動到Bob的位置時，就算Alice獲勝，相反Bob獲勝，現在Alice先手，問你誰能獲勝，
二、題解
- 當時，Alice在第一回合就能移動到Bob所在的位置，Alice獲勝，
- 當時，Alice可以移動到樹的直徑的中點(Alice的下一步移動范圍是整棵樹)，這樣無論Bob處于任何位置時，Alice都可到達Bob的位置，Alice獲勝，
- 當db <= 2 * da 時，Alice可以追上 Bob，因為Bob不能越過Alice跳到另外一顆字數上
- 當 時并且 case 1 不成立時，Alice不能一次達到Bob，Alice向Bob靠近，當Alice與Bob的距離適中大于ba時，則Bob獲勝，設；
三、ACcode
/*
* @Author: NEFU_馬家溝老三
* @LastEditTime: 2020-09-07 11:17:13
* @CSDN blog: https://blog.csdn.net/acm_durante
* @E-mail: [email protected]
* @ProbTitle:
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define lowbit(x) ((x) & -(x))
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define mem(a, b) memset(a, b, sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
const int N =2e5+5;
int cnt,head[N];
struct node
{
int v,next;
}e[N];
void add(int u,int v){
e[++cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
int dp1[N],dp2[N],dp3[N], maxx;//dp1 i節點到葉子的最大距離，dp2是次大距離，maxx是樹的直徑
//dp3是從i到a的最短距離
void dfs(int u,int fa){
for(int i = head[u]; ~i ; i = e[i].next){
int v = e[i].v;
if(v == fa) continue;
dp3[v] = dp3[u] + 1;
dfs(v,u);
if(dp1[u] < dp1[v] + 1){
dp2[u] = dp1[u];
dp1[u] = dp1[v] + 1;
}
else if(dp2[u] < dp1[v] + 1){
dp2[u] = dp1[v] + 1;
}
maxx = max(maxx,dp1[u] + dp2[u]);
}
}
int main()
{
IOS
int t;
cin >> t;
while(t--){
cnt = 0;
maxx = 0;
int n,a,b,da,db;
mem(head,-1);
mem(dp1,0);
mem(dp2,0);
mem(dp3,0);
cin >> n >> a >> b >> da >> db;
rep(i,1,n-1){
int u,v;
cin >> u >> v;
add(u,v), add(v,u);
}
dfs(a,-1);
if(da * 2 >= min(maxx,db) || da >= dp3[b] ) cout << "Alice\n";
else cout << "Bob\n";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/1488.html
標籤：區塊鏈
上一篇：Codeforces Round #668 (Div. 1) Solution
下一篇：面試常見智力題