题解 | 小红的树上游戏

import java.util.Scanner;

// 叶子：度1节点
// 若X为叶子：小红先手直接删除X节点 win

// 若X非叶子：总节点数n 偶win 奇数lose
// 归纳证明
// n<=2 先手必胜
// n==3 x不是叶子 只能 a-x-b 必输
// n==4 总是能够拿一个使得x不是叶子（要么有一个不和x相邻，要么x度是3）情况转化n==3
// n>=5 
// 对于奇数的n，不管怎么样只能转化n为偶数局面；或者把x变为叶子，也是必输
// 对于偶数的n，类似n==4的考虑，一定能够拿走一个，x不变为叶子，转化后手比败

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int n = in.nextInt(), x = in.nextInt();
            int[] deg = new int[n + 1];
            for (int i = 1; i < n; i++) {
                int u = in.nextInt(), v = in.nextInt();
                deg[u]++;
                deg[v]++;
            }
            sb.append((deg[x] == 1 || n % 2 == 0) ? "win\n" : "lose\n");
        }
        System.out.print(sb.toString());
    }
}