[题解]CF1404B Tree Tag

CF1404B Tree Tag ~ Codeforces

我们发现，若 \(db\le 2\times da\)，则说明 Bob 不能跳到 Alice 控制范围的另一侧，只能被 Alice 不断逼近到某个叶子节点，从而输掉。

不过有些情况下，Bob 的最大移动距离不是 \(db\)。因为其移动会受制于树上最长的路径，即直径 \(D\)。

所以 Alice 获胜的一个必要条件，实际上是 \(\min(db,D)\le 2\times da\)。

另外就是初始状态下 Bob 就在 Alice 的控制范围之内。

两个条件合起来就可以完成判定了。

时间复杂度 \(O(n)\)。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n,a,b,da,db,D,f[N];
vector<int> G[N];
int dfs(int u,int fa,int d){//求两点距离 if(u==b) return d;int k;for(int i:G[u]) if(i!=fa&&~(k=dfs(i,u,d+1))) return k; return -1;
}
void dfs2(int u,int fa){//求直径 for(int i:G[u]){if(i==fa) continue;dfs2(i,u);D=max(D,f[u]+f[i]+1);f[u]=max(f[u],f[i]+1);}
}
void add(int u,int v){G[u].emplace_back(v);}
bool solve(){D=0;cin>>n>>a>>b>>da>>db;for(int i=1,u,v;i<n;i++) cin>>u>>v,add(u,v),add(v,u);dfs2(1,0);int ans=min(db,D)>2*da&&dfs(a,0,0)>da;for(int i=1;i<=n;i++) G[i].clear(),f[i]=0;return ans;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>t;while(t--) cout<<(solve()?"Bob\n":"Alice\n");return 0;
}