NOIP2023模拟3联测24-博弈树

题目

由于每次移动的距离递增，考虑距离最大的时候，就是树的直径。这里的直径定义为一条包含最多点的路径。

显然，若一个点直径的一端，先手放这里一定会赢。于是“删除”原树上所有直径端点。

考虑现在的树的直径，现在树的直径的端点先手也是必胜的：如果先手放这里，先手可以把棋子移到现在直径的另一个端点，后手就只能移到原树直径的端点，先手移到另一个原树直径的端点，后手就操作不了了。

这样子每次删去直径的端点，直径的长度减少 $2$（仔细想想）。那么如果最后减少到 $1$ 时，放这个点先手必败；如果最后减少到 $2$，显然先手必胜。

结论：如果树的直径长度是奇数，那么直径中间那个点 $\text{Bob}$ 必胜，否则 $\text{Alice}$ 必胜；如果是偶数，所有的点都是 $\text{Alice}$ 必胜。

题外话，赛时我打了 70pts 暴力，剩下的就总司令（全输出 $\text{Alice}$），拿下 95pts。不可以，总司令！

#include
using namespace std;
const int N=1e5+1;
int n,q,maxdep,D;
int head[N],nxt[N<<1],to[N<<1],cnt,dep[N],fa[N];
void add(int u,int v)
{
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void dfs(int u,int f)
{
    dep[u]=dep[f]+1;
    fa[u]=f;
    if(maxdep<dep[u]){
        maxdep=dep[u];
        D=u;
    }
    for(int i=head[u];i;i=nxt[i]) if(to[i]!=f) dfs(to[i],u);
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(1,0);
    maxdep=0;
    dfs(D,0);
    if(maxdep&1){
        for(int i=1;i*2<maxdep;i++) D=fa[D];
        while(q--){
            int x;
            scanf("%d",&x);
            puts(x^D?"Alice":"Bob");
        }
    }
    else while(q--) puts("Alice");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43