NOIP2023模拟3联测24-博弈树

• NOIP2023模拟3联测24-博弈树
  • 题目大意
  • 思路
  • code

题目大意

\(Alice\) 和 \(Bob\) 又开始玩游戏了： 给定一颗 \(n\) 个节点的树，\(Alice\) 和 \(Bob\) 随机选择一个节点作为起点放上棋子，由 Alice 先手。 轮到一方后可以将这颗棋子移动到树上任意一点，每次一方移动的距离必须比对 方上一次移动的距离还要大，开始时默认为 0 。 •当一方不能再次移动之后判负。 现在 Alice 和 Bob 已经找到了一棵节点编号为 \(1 ∼ n\) 的树准备开始游戏，作为博弈 高手，\(Alice\) 和 \(Bob\) 均会做出最优的选择，选择一个节点后，他们知道游戏必然有一种 必胜策略，现在他们想知道游戏的胜负，他们会询问你 \(q\) 次，每次他们会选择一个节点 询问，你只需要回答在最优策略下以这个为节点为起点的胜者是谁即可。

\(1\le n , q \le 10^5\)

思路

显然一棵树的最长路就是直径，所以当一个人走了与直径一样长的路径的时候必胜。

现在我们假设这棵树形成了一条链，显然只有在这条链的长度是奇数且起始点在中点时先手才必败，否则先手必胜。

我们开始不断删点，每次把当前树的直径的端点删掉，如果最后能够剩下一个点，那么先手必败，否则先手必胜。

我们发现这个最后剩下的那个点一定是原树上所有直径的交点，也是他们的中点。

所以只要只有在这个树的直径是奇数且起始点在直径的中点时先手才必败，否则先手必胜。

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 1e5 + 5;
int fa[N] , n , q , dep[N] , dis[N] , hd[N] , cnt , d , ans[N];
struct E {
    int to , nt;
} e[N << 1];
void add (int x , int y) { e[++cnt].to = y , e[cnt].nt = hd[x] , hd[x] = cnt; }
void dfs1 (int x) {
    int y;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        if (y == fa[x]) continue;
        dep[y] = dep[x] + 1;
        fa[y] = x;
        dis[y] = dis[x] + 1;
        dfs1 (y);
    }
}
void dfs2 (int x , int lst) {
    int y;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        if (y == lst) continue;
        dis[y] = dis[x] + 1;
        dfs2 (y , x);
    }
}
void solve (int x , int y) {
    int sum1 = 1 , sum2 = d;
    if (dep[x] < dep[y]) swap (x , y);
    while (dep[x] != dep[y]) {
        ans[sum1] = x;
        sum1 ++;
        x = fa[x];
    }
    if (sum1 == d) return;
    while (x != y) {
        ans[sum1] = x;
        ans[sum2] = y;
        sum1 ++;
        sum2 --;
        x = fa[x];
        y = fa[y];
    }
    if (d & 1) ans[sum1] = x;
}
int main () {
    freopen ("tree.in" , "r" , stdin);
    freopen ("tree.out" , "w" , stdout);
    int u , v;
    scanf ("%d%d" , &n , &q);
    if (n == 1) {
        while (q --) puts ("Bob"); 
        return 0;
    }
    fu (i , 1 , n - 1) {
        scanf ("%d%d" , &u , &v);
        add (u , v) , add (v , u);
    }
    dfs1 (1);
    int max1 = 0 , pos1 , pos2;
    fu (i , 1 , n) {
        if (max1 < dis[i]) {
            max1 = dis[i];
            pos1 = i;
        }
    }
    
    memset (dis , 0 , sizeof (dis));
    dfs2 (pos1 , 0);
    max1 = 0;
    fu (i , 1 , n) {
        if (max1 < dis[i]) {
            max1 = dis[i];
            pos2 = i;
        }
    }
    d = max1 + 1;
    solve (pos1 , pos2);
    int mid = ans[d / 2 + 1];
    while (q --) {
        scanf ("%d" , &pos1);
        if (d & 1 && pos1 == mid) puts ("Bob");
        else puts ("Alice"); 
    }
}