题解：CF2013F1 Game in Tree (Easy Version)

· · 题解

我们考虑每个人的决策。

记 1 到 x 的路径上的点构成的序列为 b_1\sim b_m，那么假设现在 Alice 在 l，Bob 在 r，那么对于 Alice 来说，如果她要从此不再走 1 到 x 这条路径，那么就必须满足往其他地方走能走的最大步数要大于 Bob 在 [l+1,r] 处往其他地方走的最大步数，对于 Bob 也是类似。我们发现后面那个东西是一个区间最大值，所以可以预处理出每个点如果不走 b_1\sim b_m 这些点所能走到的最远点，然后直接使用 st 表维护区间最大值即可。

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

#include<bits/stdc++.h> 
using namespace std;
int t,n,a,b,u,v,st1[200005][25],st2[200005][25],fa[200005],c[200005],vis[200005],f[200005];
vector<int>ve[200005];
void dfs(int u,int f){
    fa[u]=f;
    for(int v:ve[u]){
        if(v==fa[u])continue;
        dfs(v,u);
    }
}
void dfs1(int u){
    f[u]=1;
    for(int v:ve[u]){
        if(v==fa[u])continue;
        dfs1(v);
    }
    for(int v:ve[u]){
        if(v==fa[u]||vis[v])continue;
        f[u]=max(f[u],f[v]+1);
    }
}
int query1(int l,int r){
    int k=__lg(r-l+1);
    return max(st1[l][k],st1[r-(1<<k)+1][k]);
}
int query2(int l,int r){
    int k=__lg(r-l+1);
    return max(st2[l][k],st2[r-(1<<k)+1][k]);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)ve[i].clear(),vis[i]=f[i]=0;
        for(int i=1;i<n;i++)cin>>u>>v,ve[u].emplace_back(v),ve[v].emplace_back(u);
        cin>>a>>b;
        dfs(1,0);
        int now=a,cnt=0;
        while(now)vis[now]=1,c[++cnt]=now,now=fa[now];
        dfs1(1);
        for(int i=1;i<=cnt;i++)st1[i][0]=i-1+f[c[i]]-1,st2[i][0]=cnt-i+f[c[i]]-1;
        for(int i=1;i<=20;i++)for(int j=1;j+(1<<i)-1<=cnt;j++){
            st1[j][i]=max(st1[j][i-1],st1[j+(1<<i-1)][i-1]);
            st2[j][i]=max(st2[j][i-1],st2[j+(1<<i-1)][i-1]);
        }
        int l=1,r=cnt,noww=0,flag=0;
        while(l<r){
            if(noww==0){
                int cnt1=f[c[r]]-1;
                int cnt2=query1(l,r-1)-(l-1);
                if(cnt1>cnt2){
                    cout<<"Alice\n";flag=1;
                    break;
                }
                r--;
            }
            else{
                int cnt1=f[c[l]]-1;
                int cnt2=query2(l+1,r)-(cnt-r);
                if(cnt1>cnt2){
                    cout<<"Bob\n";flag=1;
                    break;
                }
                l++;
            }
            noww^=1;
        }
        if(!flag)cout<<(noww?"Bob\n":"Alice\n");
    }
}