题解 | #小红的树上游戏#

题目链接

小红的树上游戏

题目描述

在一棵 $n$ 个节点的树上进行一个游戏。玩家轮流删除一个叶子节点及其相连的边。删除指定节点 $y$ 的玩家获胜。给定树的结构和节点 $y$ ，判断先手玩家（小红）是否必胜。

解题思路

这是一个典型的公平博弈问题。胜负的关键在于分析游戏的状态和玩家的回合。制胜的关键是操作使得目标节点 $y$ 成为一个叶子节点，并在自己的回合将其移除。

我们可以分两种情况来讨论：

情况一：目标节点 $y$ 初始就是叶子节点

如果节点 $y$ 在游戏开始时就是一个叶子节点，它的度数 deg(y) 为 1 (或在只有一个节点 $n=1$ 的特殊情况下为0)。

小红是先手玩家，她可以在第一回合直接选择删除节点 $y$ ，从而立即获胜。

情况二：目标节点 $y$ 初始不是叶子节点 (`deg(y) > 1`)

如果 $y$ 不是叶子，小红就不能在第一步获胜。游戏会继续下去，直到 $y$ 成为叶子为止。此时，胜负手取决于当 $y$ 成为叶子时，轮到谁的回合。

游戏进程的本质：每一次操作（删除一个叶子节点）都会从树上移除一个节点和一条边。
达成胜利的前提：为了让 $y$ 能被移除，它必须先变成叶子节点。这意味着与 $y$ 相连的所有边，除了最后一条，都必须被移除。
计算所需步数：一棵 $n$ 个节点的树有 $n-1$ 条边。要让 $y$ 成为叶子，并且仍然连通于树的某个部分（即保留一条边），那么树上其余的 (n-1) - 1 = n-2 条边都必须被移除。
步数与玩家回合：由于每一步操作移除一条边，所以将 $y$ 变为叶子节点，需要且必须经过 n-2 步操作。完成这 n-2 步之后，游戏进入第 n-1 步，此时 $y$ 成为可移除的叶子。执行第 n-1 步的玩家将获胜。

现在我们来判断第 n-1 步由谁执行：

第 1 步：小红 (先手)
第 2 步：朋友 (后手)
...
第 $k$ 步：如果 $k$ 是奇数，由小红执行；如果 $k$ 是偶数，由朋友执行。

因此，胜负取决于 n-1 的奇偶性：

如果 n-1 是奇数，小红将执行第 n-1 步并获胜。这种情况发生在 $n$ 是偶数时。
如果 n-1 是偶数，朋友将执行第 n-1 步，小红将失败。这种情况发生在 $n$ 是奇数时。

结论

结合两种情况，小红的必胜策略如下：

计算节点 $y$ 的度数 deg(y)。
如果 deg(y) <= 1，小红胜。
否则，判断 n-1 的奇偶性。如果 n-1 是奇数（即 $n$ 是偶数），小红胜。
其他情况，小红败。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, y;
    cin >> n >> y;
    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[y] <= 1) {
        cout << "win" << endl;
    } else {
        // n-2 a total of n-2 moves are made before y becomes a leaf.
        // It's the (n-1)th move that removes y.
        // If n-1 is odd, the first player wins.
        if ((n - 1) % 2 != 0) {
            cout << "win" << endl;
        } else {
            cout << "lose" << endl;
        }
    }
}

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) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        int y = 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[y] <= 1) {
            System.out.println("win");
        } else {
            // It takes n-2 moves to make y a leaf.
            // The winning move is the (n-1)-th move.
            // If n-1 is odd, player 1 (first player) makes the move.
            if ((n - 1) % 2 != 0) {
                System.out.println("win");
            } else {
                System.out.println("lose");
            }
        }
    }
}

import sys

def solve():
    n, y = map(int, sys.stdin.readline().split())
    degree = [0] * (n + 1)
    # The actual edges don't matter beyond degree calculation for this problem
    for _ in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        degree[u] += 1
        degree[v] += 1
    
    # Case 1: y is already a leaf. First player wins.
    if degree[y] <= 1:
        print("win")
        return

    # Case 2: y is not a leaf.
    # It takes n-2 moves to make y a leaf.
    # The (n-1)th move is the winning move.
    # If n-1 is odd, it's the first player's turn.
    if (n - 1) % 2 == 1:
        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()

if __name__ == "__main__":
    main()

算法及复杂度

算法：图论 + 博弈论
时间复杂度：对于每组测试数据，我们需要读取 $n-1$ 条边来计算节点的度数。这个过程的时间复杂度是 $\mathcal{O}(n)$ 。之后的判断是 $\mathcal{O}(1)$ 。因此，总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：我们需要一个数组来存储每个节点的度数，所以空间复杂度是 $\mathcal{O}(n)$ 。