CF1404BTree Tag/ BZOJ0487. 树上追逐详解

1.题目

传送门:Tree Tag - 洛谷

2.思路

我们考虑什么情况下Alice可以获胜.

如果 $dis_{a,b}$ ≤ da，则Alice可以一步就追上Bob.

如果Alice处在一个能覆盖整棵树的点，即2da + 1≥树的直径，那么Bob也无论走到哪里Alice都能追到,Alice获胜.

其它情况下，Alice会一步一步逼近Bob，并一定能把Bob逼近某棵子树.

如果当前Alice占据一个点，使Bob无论怎么走都还在Alice的控制范围内，那么Alice必胜.

此时条件即为2da≥db.

最后一种情况有些同学可能没听懂，我来举个栗子

那么此时如果是Bob走，并且满足2da≥db的话

如果Bob继续往下走，Alice肯定能继续追(其实Bob只能往下走，不然一步就会被追上)，而当Bob走到一个子节点，没办法往下走的时候，那么他就必输

除以上条件外，Bob获胜，因为他可以再Alice靠近他的时候不断反向跳走.

总结一下:

只有三种情况 Alice 赢

dis(a,b)≤da
2×da≥db 此时只要一步步逼近即可
树的直径 ≤2×da 此时只要占据直径中点即可

3.代码

#include <bits/stdc++.h>
using namespace std;
int t,n,a,u,v,b,da,db,deep[1000001],deep_2[1000001],zj,zjj,lzj;
vector<int> vec[1000001];
void dfs(int x,int fa,int d)
{deep[x] = d;for(int i = 0;i < vec[x].size();i++)if(vec[x][i] != fa)dfs(vec[x][i],x,d + 1);
}
void qzj()//求树的直径
{dfs(1,0,0);int t = 0;for(int i = 1;i <= n;i++)if(t < deep[i]){t = deep[i];zj = i;}dfs(zj,0,0);t = 0;for(int i = 1;i <= n;i++)if(t < deep[i]){t = deep[i];zjj = i;}lzj = t;
}
int main()
{cin>>t;while(t--){cin>>n>>a>>b>>da>>db;for(int i = 1; i <= n; i++) vec[i].clear();for(int i = 1;i < n;i++){cin>>u>>v;vec[u].push_back(v);vec[v].push_back(u);}if(2 * da >= db){cout<<"Alice\n";continue;}qzj();if(2 * da >= lzj){cout<<"Alice\n";continue;}dfs(a,0,0);if(deep[b] <= da){cout<<"Alice\n";continue;}cout<<"Bob\n";}return 0;
}