小红的树上游戏

[题目链接](https://www.nowcoder.com/practice/40b3fc91da024acc93ffd70c695b5d41)

思路

两人轮流从树上删除叶子节点（度 的节点），谁删除节点 谁就赢。小红先手，判断她是否有必胜策略。

情况一： 是叶子节点

如果 的度数 ，即 本身就是叶子节点，小红第一步直接删除 即可获胜。

情况二： 不是叶子节点

当 时， 不能被立刻删除，双方每一步只能删除某个非 的叶子节点。此时结论是： 为偶数先手胜， 为奇数先手负。

为什么是 的奇偶性？

关键观察：当 不是叶子时，每一步操作都是"删除一个非 的叶子"。我们来证明：无论双方怎么操作， 总是最后一个被删除的节点。

考虑在某个时刻， 变成了叶子（度数为 1），此时它与唯一邻居 相连。当前玩家可以选择删 （获胜），也可以删别的叶子。但如果当前玩家不想让对手赢，他不会去删 的子树中的节点让 变成孤立点——因为在 是叶子的时候，当前玩家直接就可以拿走 。

更严格地说：如果当前 不是叶子，当前玩家删除一个叶子后， 可能变成叶子，也可能不变。无论如何，双方都在"消耗"非 节点。由于 的度数 ，一个非 叶子的删除最多让 的度数减 1。可以证明双方都有策略保证：只要 变成叶子，当前操作者就能立即拿走它。因此， 实际上等价于最后被删除的节点（第 步），删除 的是第 步的操作者。 为奇数时后手操作第 步（小红输）， 为偶数时先手操作第 步（小红赢）。

等等，这里的推理需要更精细。实际上正确的论证思路是：

  • 对于 的情况，可以用博弈论归纳证明：无论树的形态如何，双方最优策略下， 恰好在第 步被删除。
  • 直觉上，对手总可以"模仿"先手的策略来维持奇偶性。如果先手试图在某个奇数步让 变成叶子，对手可以在别的分支操作来阻止；反之亦然。最终 必然最后被删，胜负只取决于 的奇偶。

总结

$$

\text{答案} = \begin{cases}

\texttt{win}, & \deg(k) \leq 1 \\

\texttt{win}, & \deg(k) \geq 2 \text{ 且 } n \text{ 为偶数} \\

\texttt{lose}, & \deg(k) \geq 2 \text{ 且 } n \text{ 为奇数}

\end{cases}

$$

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        vector<int> deg(n + 1, 0);
        for(int i = 0; i < n - 1; i++){
            int u, v;
            cin >> u >> v;
            deg[u]++;
            deg[v]++;
        }
        if(deg[k] <= 1){
            cout << "win\n";
        } else {
            cout << (n % 2 == 0 ? "win" : "lose") << "\n";
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            int[] deg = new int[n + 1];
            for (int i = 0; i < n - 1; i++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                deg[u]++;
                deg[v]++;
            }
            if (deg[k] <= 1) {
                sb.append("win\n");
            } else {
                sb.append(n % 2 == 0 ? "win" : "lose").append("\n");
            }
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    deg = [0] * (n + 1)
    for i in range(n - 1):
        u, v = map(int, input().split())
        deg[u] += 1
        deg[v] += 1
    if deg[k] <= 1:
        print("win")
    else:
        print("win" if n % 2 == 0 else "lose")

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const t = parseInt(lines[idx++]);
    const res = [];
    for (let i = 0; i < t; i++) {
        const [n, k] = lines[idx++].split(' ').map(Number);
        const deg = new Array(n + 1).fill(0);
        for (let j = 0; j < n - 1; j++) {
            const [u, v] = lines[idx++].split(' ').map(Number);
            deg[u]++;
            deg[v]++;
        }
        if (deg[k] <= 1) {
            res.push("win");
        } else {
            res.push(n % 2 === 0 ? "win" : "lose");
        }
    }
    console.log(res.join('\n'));
});

复杂度分析

  • 时间复杂度: ，每组测试用例只需读入边并统计度数。
  • 空间复杂度: ，存储度数数组。