Codeforces Round 668 (Div. 1) B题 Tree Tag

题目链接

https://codeforces.com/problemset/problem/1404/B

思路

只有三种情况Alice会赢：

1. $dis(a,b)\le da$，第一步就直接获胜
2. $da\times 2\ge db$，可以不断逼近Bob
3. $da\times 2\le 树的直径$，此时只需要先占据直径中点即可（参考第一个样例）

否则，Bob会赢。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, a, b, da, db;
int dis[N];
vector<int>mp[N];
void dfs(int u, int fu, int dist)
{
dis[u] = dist;
for (int j : mp[u])
{
if (j == fu) continue;
dfs(j, u, dist + 1);
}
}
void solve()
{
cin >> n >> a >> b >> da >> db;
for (int i = 1; i <= n; i++)
{
mp[i].clear();
}
for (int i = 1, u, v; i < n; i++)
{
cin >> u >> v;
mp[u].push_back(v);
mp[v].push_back(u);
}
if (da * 2 >= db)
{
cout << "Alice" << endl;
return;
}
dfs(a, -1, 0);
if (dis[b] <= da)
{
cout << "Alice" << endl;
}
else
{
int maxx = *max_element(dis + 1, dis + 1 + n);
int idx = a;
for (int i = 1; i <= n; i++)
if (dis[i] == maxx)
idx = i;

dfs(idx, -1, 0);
int dia = *max_element(dis + 1, dis + 1 + n);
if (dia <= da * 2)
{
cout << "Alice" << endl;
}
else cout << "Bob" << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}

原文地址：https://blog.csdn.net/weixin_74754298/article/details/142570193

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！