题解：机场炸弹游戏

题目分析

这道题目描述了一个基于树形结构的博弈游戏：

1. 游戏在一个由$N$个机场和$N-1$条航班构成的树形结构上进行
2. 两名玩家轮流操作，每次选择一个相邻机场放置炸弹并飞往该机场
3. 被炸毁的机场及其连接边从游戏中移除
4. 无法操作的玩家输掉游戏
5. 需要判断在双方都采取最优策略的情况下，先手玩家是否能必胜

算法思路

这个问题可以转化为博弈论中的"树上删边游戏"，可以使用Grundy数（博弈论中的必胜策略判定方法）来解决：

1. 树形结构处理：将机场和航班建模为无向树
2. Grundy数计算：通过深度优先搜索计算每个节点的Grundy数
3. 胜负判断：根据根节点（起始机场）的Grundy数判断先手胜负
4. 必胜策略：如果先手必胜，找出编号最小的必胜移动

数学原理

Grundy数的计算遵循以下规则：

• 叶子节点的Grundy数为$0$
• 非叶子节点的Grundy数为所有子节点Grundy数$+1$的异或和
• 游戏胜负判定：
  • 若根节点Grundy数$G \neq 0$，先手必胜
  • 若$G = 0$，先手必败

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

vector<vector<int>> adj;  // 邻接表存储树结构
vector<int> grundy;       // 存储每个节点的Grundy数

// 深度优先搜索计算Grundy数
void dfs(int u, int parent) {
    grundy[u] = 0;  // 初始化当前节点的Grundy数为$0$
    
    // 遍历所有相邻节点
    for (int v : adj[u]) {
        if (v != parent) {  // 避免回溯到父节点
            dfs(v, u);      // 递归计算子节点的Grundy数
            grundy[u] ^= (grundy[v] + 1);  // 异或操作计算当前节点的Grundy数
        }
    }
}

int main() {
    int N, K;
    cin >> N >> K;  // 读取机场数量和起始机场
    
    // 初始化邻接表和Grundy数组
    adj.resize(N + 1);
    grundy.resize(N + 1);

    // 读取航班信息并构建邻接表
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);  // 无向图，双向添加
        adj[v].push_back(u);
    }

    // 从起始机场开始计算Grundy数
    dfs(K, -1);  // -1表示没有父节点

    // 判断游戏结果
    if (grundy[K] != 0) {  // 如果根节点Grundy数不为$0$，先手必胜
        int min_airport = INT_MAX;  // 初始化最小机场编号
        
        // 寻找最优移动（编号最小的必胜移动）
        for (int v : adj[K]) {
            // 检查移动到$v$是否能使得对手处于必败态
            if ((grundy[K] ^ (grundy[v] + 1)) == 0) {
                min_airport = min(min_airport, v);  // 更新最小编号
            }
        }
        cout << "First player wins flying to airport " << min_airport << endl;
    } else {  // 先手必败
        cout << "First player loses" << endl;
    }

    return 0;
}

复杂度分析

1. 时间复杂度：$O(N)$
   • DFS遍历整个树：$O(N)$
   • 寻找最优移动：$O(\text{deg}(K))$，其中$\text{deg}(K)$是起始节点的度数
2. 空间复杂度：$O(N)$
   • 邻接表存储：$O(N)$
   • Grundy数组：$O(N)$