题解

比较基础的博弈论

• 如果目标节点x在环中，结果必然是平局(Draw)。
• 如果x不在环中:
• 计算在删除x之前(包括x)可删除的节点数cnt。
• cnt为偶数，Xiaoyo无法删除该点，Pyrmont获胜。
• cnt为奇数，Xiaoyo获胜。

特殊情况：

• x在环中：结果为Draw。
• x初始度数为1：Xiaoyo直接获胜。

代码

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

void solve()
{
    int n, x;
    cin >> n >> x;
    vector<vector<int>> adj_list(n + 1);
    vector<int> degree(n + 1, 0);

    for (int i = 0; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

    deque<int> queue;
    for (int i = 1; i <= n; ++i)
    {
        if (degree[i] == 1)
        {
            if (i == x)
            {
                cout << "Xiaoyo" << endl;
                return;
            }
            queue.push_back(i);
        }
    }

    int removed_count = 0;
    bool target_found = false;
    while (!queue.empty())
    {
        int current = queue.front();
        queue.pop_front();
        removed_count++;
        if (current == x)
        {
            target_found = true;
            continue;
        }
        for (int neighbor : adj_list[current])
        {
            degree[neighbor]--;
            if (degree[neighbor] == 1)
            {
                queue.push_back(neighbor);
            }
        }
    }

    if (!target_found)
    {
        cout << "Draw" << endl;
    }
    else if (removed_count % 2 == 0)
    {
        cout << "Pyrmont" << endl;
    }
    else
    {
        cout << "Xiaoyo" << endl;
    }
}

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

java

import java.util.*;

public class Main {

    // 处理每组测试数据的函数
    public static void solve(Scanner sc) {
        int n = sc.nextInt();  // 读取节点数 n
        int x = sc.nextInt();  // 读取目标节点 x

        // 创建邻接表来表示树的结构
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());  // 初始化每个节点的邻接列表
        }

        // 度数数组，用来存储每个节点的度数
        int[] degree = new int[n + 1];

        // 读取树的边，并构建邻接表
        for (int i = 0; i < n; i++) {
            int u = sc.nextInt();  // 读取一条边的一个节点 u
            int v = sc.nextInt();  // 读取这条边的另一个节点 v
            adjList.get(u).add(v);  // 在 u 的邻接列表中添加 v
            adjList.get(v).add(u);  // 在 v 的邻接列表中添加 u
            degree[u]++;  // 增加 u 的度数
            degree[v]++;  // 增加 v 的度数
        }

        // 使用双端队列（deque）来模拟叶子节点的队列
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (degree[i] == 1) {  // 如果节点 i 是叶子节点
                if (i == x) {  // 如果这个叶子节点正好是目标节点 x
                    System.out.println("Xiaoyo");  // Xiaoyo 直接胜利
                    return;  // 直接结束这次测试
                }
                queue.addLast(i);  // 将叶子节点添加到队列末尾
            }
        }

        int removedCount = 0;  // 记录被移除的节点数
        boolean targetFound = false;  // 标记是否找到目标节点 x

        // 处理队列中的节点，模拟移除叶子节点的过程
        while (!queue.isEmpty()) {
            int current = queue.pollFirst();  // 从队列前端取出一个节点
            removedCount++;  // 增加被移除的节点计数
            if (current == x) {  // 如果当前节点是目标节点 x
                targetFound = true;  // 标记已找到目标节点
                continue;  // 继续处理其他节点
            }
            // 对当前节点的每个邻居节点进行处理
            for (int neighbor : adjList.get(current)) {
                degree[neighbor]--;  // 当前节点被移除后，邻居节点的度数减 1
                if (degree[neighbor] == 1) {  // 如果邻居节点变成了叶子节点
                    queue.addLast(neighbor);  // 将它添加到队列末尾
                }
            }
        }

        // 根据是否找到目标节点以及被移除的节点数判断结果
        if (!targetFound) {
            System.out.println("Draw");  // 如果没有找到目标节点，结果是平局
        } else if (removedCount % 2 == 0) {
            System.out.println("Pyrmont");  // 如果移除的节点数为偶数，Pyrmont 胜利
        } else {
            System.out.println("Xiaoyo");  // 如果移除的节点数为奇数，Xiaoyo 胜利
        }
    }

    // 主函数，用于处理多个测试用例
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();  // 读取测试组数 T
        while (T-- > 0) {  // 逐组处理测试数据
            solve(sc);  // 调用 solve 函数处理每组数据
        }
        sc.close();  // 关闭输入流
    }
}

题目描述

米小游正在玩一个有趣的游戏。这个游戏在一个特殊的图结构——基环树（点数与边数相等的无向简单连通图）上进行。在这个游戏中，米小游选择的角色 Xiaoyo 和他的对手 Pyrmont 轮流进行操作：（定义度数为与这个点相连的边数）

• 选择图中一个度数为 $1$ 的点，删除这个点以及与这个点相连的边。

在图中有一个特殊的点 $x$，删除点 $x$ 的玩家即获胜。

现在，米小游（Xiaoyo）先进行操作。在双方都采取最优策略的情况下，谁将成为最终的胜者呢？

输入格式

第一行输入一个整数 $T$，代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n$，$x$，表示图的点数及特殊点的编号。

接下来 $n$ 行，第 $i$ 行两个整数 $u_i$ 和 $v_i$，表示树上第 $i$ 条边连接节点 $u_i$ 和 $v_i$。保证图联通，没有重边。

除此之外，保证给定的边构成一个基环树，所有的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对于每一组测试数据，在一行上输出胜者的名字（ $\verb!Xiaoyo!$ 或 $\verb!Pyrmont!$ ）。特别地，若点 $x$ 不可能被删除，请输出 $\verb!Draw!$ 。

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

Xiaoyo
Pyrmont
Draw

范围

对于 $100\%$ 的数据，满足 $1\le T\le 1000$，$3\le n\le 10^5$，$1\le v_i,u_i\le n, u_i\ne v_i$。