Codeforces Round 973 (Div. 2) F1. Game in Tree (Easy Version)（思维题 博弈）

题目

思路来源

乱搞ac

题解

两个人的策略是一样的，把1到u的路径标记，

如果能走旁边的链（也就是当前点，刨去标记链以外的子树中最长的链），

使得对面走剩余的连通块无法比你大，就走旁边的链，并宣告获胜

否则沿着标记链，朝对面的方向走一步

维护实际是一个区间最值，可以用set或者st表

代码

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int t,n,u,v,f[N],g[N],to;
vector<int>e[N],tmp;
set<P>my,your;
bool is[N];
void dfs(int u,int fa){f[u]=0;for(auto &v:e[u]){if(v==fa)continue;dfs(v,u);if(is[v])is[u]=1;else f[u]=max(f[u],f[v]+1);}if(u==1 || u==to)is[u]=1;if(is[u])tmp.pb(u);
}
int main(){sci(t);while(t--){sci(n);rep(i,1,n)e[i].clear(),is[i]=0;rep(i,2,n){sci(u),sci(v);e[u].pb(v);e[v].pb(u);}sci(to);sci(to);tmp.clear();dfs(1,0);rep(i,1,n)g[i]=f[i];tmp.clear();dfs(to,0);my.clear();your.clear();int cm=0,cy=0;for(auto &v:tmp){g[v]+=cm;cm++;if(v==to)break;my.insert(P(g[v],v));}reverse(tmp.begin(),tmp.end());for(auto &v:tmp){f[v]+=cy;cy++;if(v==1)break;your.insert(P(f[v],v));}reverse(tmp.begin(),tmp.end());int op=0,l=0,r=SZ(tmp)-1,nm=0,ny=0;while(SZ(my) || SZ(your)){if(op==0 && !SZ(my))break;if(op==1 && !SZ(your))break;if(op==0){int p=tmp[l],yy=SZ(your)==0?0:(*your.rbegin()).fi;if(g[p]>max(ny,yy)){nm=g[p];break;}if(l+1<r){my.erase(P(g[p],p));p=tmp[++l];your.erase(P(f[p],p));nm=l;}else{nm=g[p];ny=max(ny,yy);break;}}else{int p=tmp[r],mm=SZ(my)==0?0:(*my.rbegin()).fi;if(f[p]>=max(nm,mm)){ny=f[p];break;}if(l+1<r){your.erase(P(f[p],p));p=tmp[--r];my.erase(P(g[p],p));ny=SZ(tmp)-1-r;}else{ny=f[p];nm=max(nm,mm);break;}}op^=1;}puts(nm>ny?"Alice":"Bob");}return 0;
}