题目链接

小红的树上游戏

题目描述

在一棵 个节点的无根树上，小红和朋友轮流删除叶子节点。若某位玩家删除了一个特殊的节点 ，则该玩家立即获胜。双方都采取最优策略，小红先手，判断她是否必胜。

解题思路

本题是一个博弈问题。由于双方都采取最优策略，我们需要找到决定游戏胜负的根本性质。

1. 直接获胜条件

游戏最简单的情况是，特殊节点 在游戏开始时就是一个叶子节点（度数为），或者是一个孤立点（度数为，当 时）。在这种情况下，小红作为先手，可以在她的第一个回合直接删除节点 并获胜。因此，这是一个必胜条件。

2. 游戏过程分析

如果节点 的初始度数大于，游戏将继续。双方轮流移除叶子节点。

  • 游戏目标：轮到自己时，使节点 成为一个叶子节点，从而可以删除它获胜。

  • 最优策略：如果不能立即获胜，就阻止对方获胜。

游戏的进程是不断地“修剪”树的枝叶。我们可以把这个过程看作是消耗树上的节点。每回合，一个节点被移除。游戏的关键转折点发生在节点 变为叶子节点的那一刻。

3. 寻找不变量与胜负手

让我们考虑一下，在双方都阻止对方“抄近道”的情况下，这场游戏会持续多久。一个玩家移除一个叶子节点，节点总数减一。只要树上还有两个以上的节点，就必然存在至少两个叶子。只要 不是唯一的节点，游戏就可以继续。

在双方的最优策略下，他们会互相抵消对方想“抄近道”使 提前成为叶子的企图。这种攻防最终会使游戏趋向于消耗掉所有“安全”的节点。

游戏最终会进行到只剩下节点 和它的最后一个邻居为止。此时，树的形态是一条边连接着两个节点，这两个节点都是叶子。

  • 假设移除所有其他 个节点需要 个回合。

  • 在第 回合结束后，轮到第 回合的玩家。他会看到节点 和它的最后一个邻居都是叶子。根据最优策略，他会选择删除 并获胜。

因此，胜负手在于谁执掌第 回合。

  • 小红的回合是第 回合。

  • 朋友的回合是第 回合。

小红若想获胜，她必须在奇数回合轮到她时，面临 是叶子节点的情况。根据我们的分析，这个关键的回合是第 回合。

  • 若 是奇数（即 是偶数），则第 回合是小红的回合，小红必胜。

  • 若 是偶数（即 是奇数），则第 回合是朋友的回合，小红必败。

结论

  1. 计算特殊节点 的度数 。如果 ，小红先手必胜。

  2. 如果 ，则判断游戏剩余的步数。在最优策略下，双方会移除 个“非关键”节点，直到只剩下 和它的一个邻居。这需要 步。第 步的玩家将获胜。

    • 如果 是偶数，那么第 步轮到先手（小红）。小红必胜。

    • 如果 是奇数，那么第 步轮到后手（朋友）。小红必败。

    • 这等价于判断 的奇偶性： 为偶数则小红胜， 为奇数则小红败。

代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> degree(n + 1, 0);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;
    }

    if (degree[x] <= 1) {
        cout << "win\n";
        return;
    }

    // 移除非关键的 N-2 个节点后，轮到第 N-1 个玩家。
    // 如果 (N-2) 为偶数，则第 N-1 步轮到先手（小红）。
    // 如果 (N-2) 为奇数，则第 N-1 步轮到后手。
    if ((n - 2) % 2 == 0) {
        cout << "win\n";
    } else {
        cout << "lose\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int x = sc.nextInt();
            int[] degree = new int[n + 1];
            for (int i = 0; i < n - 1; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                degree[u]++;
                degree[v]++;
            }

            if (degree[x] <= 1) {
                System.out.println("win");
                continue;
            }

            // 移除非关键的 N-2 个节点后，轮到第 N-1 个玩家。
            // 如果 (N-2) 为偶数，则第 N-1 步轮到先手（小红）。
            // 如果 (N-2) 为奇数，则第 N-1 步轮到后手。
            if ((n - 2) % 2 == 0) {
                System.out.println("win");
            } else {
                System.out.println("lose");
            }
        }
    }
}

import sys

def solve():
    line = sys.stdin.readline()
    if not line: return
    n, x = map(int, line.split())
    degree = [0] * (n + 1)
    
    edges = []
    for _ in range(n - 1):
        edges.append(list(map(int, sys.stdin.readline().split())))

    for u, v in edges:
        degree[u] += 1
        degree[v] += 1

    if degree[x] <= 1:
        print("win")
        return

    # 移除非关键的 N-2 个节点后，轮到第 N-1 个玩家。
    # 如果 (N-2) 为偶数，则第 N-1 步轮到先手（小红）。
    # 如果 (N-2) 为奇数，则第 N-1 步轮到后手。
    if (n - 2) % 2 == 0:
        print("win")
    else:
        print("lose")

def main():
    t_str = sys.stdin.readline()
    if not t_str: return
    t = int(t_str)
    for _ in range(t):
        solve()

main()

算法及复杂度

  • 算法：计算度数，根据奇偶性判断。

  • 时间复杂度：。

    • 读入 条边并计算所有节点的度，需要 的时间。

    • 判断和输出是常数时间操作。

    • 对于每组测试数据，总体时间复杂度为 。

  • 空间复杂度：。

    • 需要一个大小为 的数组来存储每个节点的度数。