思路:图论 博弈论

解决这个问题的关键在于如何判断是否有可能删除编号为$x$的节点。

我们可以观察到，如果编号为$x$的节点是叶子节点，那么可以直接删除它并获胜。如果编号为$x$的节点不是叶子节点，那么需要通过一系列的操作，使得编号为$x$的节点变成叶子节点，然后删除它。

具体实现时，我们可以首先构建出给定的树，然后检查编号为$x$的节点的度（即它连接的边的数量）。如果它的度小于等于1，那么它是叶子节点，塔子哥可以直接删除它并获胜。如果它的度大于1，那么我们需要检查树的节点数量是否为偶数。如果是偶数，那么有可能通过一系列的操作，使得编号为$x$的节点变成叶子节点，然后删除它。如果是奇数，则无法获胜。

简单证明

如果树的节点数量是偶数，那么作为先手玩家可以通过一种叫做"对称策略"的方法来确保获胜。具体来说，他可以模仿对手的操作：如果对手删除了一个叶子节点，那么他就删除另一个叶子节点。这样，无论对手如何操作，都可以确保在他的回合结束后，树的节点数量仍然是偶数。因此，当树的节点数量减少到2时，就可以删除编号为$x$的节点并获胜。

如果树的节点数量是奇数，那么就不能使用这种策略。因为无论他如何操作，都不能确保在他的回合结束后，树的节点数量仍然是偶数。因此，对手可以通过一系列的操作，使得在他的回合，树的节点数量为3。这样，塔子哥就无法删除编号为x的节点，因此他就输了游戏。

代码

C++

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

void solve(){
    int n,x;
    cin >> n >> x;
    int cnt = 0;
    for (int i = 1; i < n; ++ i){
        int u, v;
        cin >> u >> v;
        if (u == x || v == x) cnt ++;
    }
    if (cnt == 1) {
        cout << "win\n";
        return;
    }
    if (((n-1-cnt)%2 == 1) ^ (cnt%2 == 1))
        cout << "win\n";
    else
        cout << "lose\n";
}

int main(){
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int gg = 0; gg < t; gg++) {
            int n = sc.nextInt();
            int x = sc.nextInt();
            List<List<Integer>> e = new ArrayList<>();
            for (int i = 0; i <= n; i++) {
                e.add(new ArrayList<>());
            }
            for (int i = 0; i < n - 1; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                e.get(u).add(v);
                e.get(v).add(u);
            }
            if (e.get(x).size() <= 1 || (n - 2) % 2 == 0) {
                System.out.println("win");
            } else {
                System.out.println("lose");
            }
        }
    }
}

Python

t = int(input())

def dfs(u, fa):
    sumv = 1
    for v in e[u]:
        if v == fa:
            continue
        sumv += dfs(v, u)
    return sumv

for _ in range(t):
    n, x = map(int, input().split())
    e = [[] for _ in range(n + 1)]
    # cnt = [0]
    for _ in range(n-1):
        u, v = map(int, input().split())
        e[u].append(v)
        e[v].append(u)
    cnt = []
    # for u in e[x]:
    #     cnt.append(dfs(u, x))
    # if len(cnt) <= 1 or n % 2 == 0:
    if len(e[x]) <= 1 or n % 2 == 0:
        print('win')
    else:
        print('lose')

题目描述

小红在和他的朋友博弈，规则如下：给定一棵树，每次可以删除叶子节点，删除编号为x的获胜。问小红能不能获胜。

输入描述

第一行输入一个整数 $t$，表示数据组数。每组数据第一行两个整数 $n$ 和$x$，表示树的结点数和获胜条件。

接下来 $n-1$行，每行两个整数 $u$ 和$v$，表示树上存在一条连接$u$和$v$的边。

$1 \leq t \leq 30$

$1 \leq n \leq 10^4$

1$\leq u,v,x \leq n$

输出描述

输出$t$行，每行一个字符串，如果小红能获胜，输出 $win$，否则输出 $lose$。

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

2
3 2
1 2
1 3
5 1
1 2
1 3
1 4
2 5

输出

win
lose

说明

第一组，$2$ 是叶子结点，可以直接删除