当前位置：首页 > news >正文

AT_abc398_e [ABC398E] Tree Game 题解

news 来源：原创 2025/9/1 15:50:57

题目传送门

题目大意

题目描述

本题是一道交互题（你的程序需要通过输入输出与评测系统进行交互）。

给定一棵包含 $N$ 个顶点的树 $G$ ，顶点编号为 $1$ 至 $N$ 。第 $i$ 条边连接顶点 $U_i$ 和 $V_i$ 。

你和高桥君将使用这棵树 $G$ 进行游戏。首先，你选择先手或后手。之后，双方轮流进行以下操作（先手先行动）：

选择一个满足 $\leq i < j \leq N$ 的整数对 $(i, j)$ ，并满足以下两个条件：
- $G$ 中当前不存在连接顶点 $i$ 和顶点 $j$ 的边。
- 在 $G$ 中添加连接顶点 $i$ 和顶点 $j$ 的边后，不会形成奇环。
将该边添加到 $G$ 中。

无法进行操作的一方判负，另一方获胜。请通过实际与高桥君对弈取得胜利。

奇环的定义：顶点序列 $(v_0, v_1, \ldots, v_k)$ 满足以下所有条件时，称为 $G$ 的一个奇环：

$k$ 为奇数。
$v_0 = v_k$ 。
对所有 $\leq i \leq k$ ，存在连接 $v_{i-1}$ 和 $v_i$ 的边。

交互方式

本题是一道交互题，你的程序需通过标准输入输出与评测系统交互。

首先，通过标准输入接收 $N$ 及 $G$ 的信息，格式如下：

$N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

接着，你需决定选择先手或后手。若选择先手，通过标准输出输出 First；若选择后手，输出 Second。

此后游戏开始。

你的回合时，需将选择的整数对 $(i, j)$ 按顺序以空格分隔输出至标准输出：

$i$ $j$

高桥君的回合时，将通过标准输入给出两个整数 $i$ 和 $j$ ：

$i$ $j$

当 $(i, j) = (- 1, - 1)$ 时，表示你已获胜且游戏结束，此时需立即终止程序。
其他情况下， $(i, j)$ 表示高桥君选择的整数对。

输入格式

见「交互方式」。

输出格式

见「交互方式」。

说明/提示

约束条件

$\leq N \leq 100$
$\leq U_i < V_i \leq N$
给定的图是树。
输入均为整数。

注意事项

$\footnotesize\color{red}\textsf{\textbf{每次输出后，需在末尾添加换行符并刷新标准输出缓冲区。否则可能导致评测结果为 \colorbox{#f0ad4e}{\color{white}{TLE}}。}}$
若在交互过程中输出格式错误或程序意外终止，评测结果将不确定。
游戏结束后请立即终止程序，否则评测结果不确定。

交互示例

输入	输出	解释
$\begin{matrix} \texttt{4 { }} \\ \texttt{1 2} \\ \texttt{2 3} \\ \texttt{3 4} \end{matrix}$		首先，你收到 $N$ 和 $G$ 的边信息。
	$\texttt{First}$	你选择先手行动。
	$\texttt{1 4}$	你在顶点 $1$ 和 $4$ 之间添加一条边
$\texttt{-1 -1}$		高桥无法继续操作，你获胜。评测结果返回 $\colorbox{#5cb85c}{\footnotesize\textsf{\textbf{\color{white}{AC}}}}$ 。

解题思路

题目要求我们没有奇环，所以我们将这棵树进行二分图染色（父节点与子节点的颜色不一样且只有两种颜色）。然后我们暴力查找所有没有连过边且颜色相异的 $i, j$ ，将 $(i, j)$ 存下来。如果存下来的边数为奇数，那么选择先手，否则后手。

因为如果环为奇环那么首尾位颜色一定一样，比如 $\to 1 \to 0$ ，而偶环 $\to 1 \to 0 \to 1$ 首尾位置颜色不同，并且这个环一定是树上的一条路径再加上一条我们自己连的边，所以显然。

至于先手后手应该不难理解吧，例如有 $3$ 条边，如果你后手，那么高桥选 $1$ 条，你又选 $1$ 条，最后高桥选 $1$ 条，到你的时候发现不管怎么选都会构成奇环，所以只能先手，证明偶数后手同理。

接下来我们就只需要标记所有出现过的 $(i, j)$ ，再找到没有标记过的 $(x, y)$ 输出即可。

CODE：

//ChatGPT 添加的注释
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> v[N];
vector<pair<int, int >> v2;
map<pair<int, int>, bool > m;
bool color[N];  // 用于标记每个节点的颜色（0 或 1）
inline void dfs(int x, int fa) {color[x] = color[fa] ^ 1;  // 当前节点的颜色与父节点颜色不同for (auto u : v[x]) {if (u ^ fa) {dfs(u, x);}}
}
int main() {
//	ios::sync_with_stdio(false);
//	ios_base::sync_with_stdio(false);
//	cin.tie(0), cout.tie(0);int n;cin >> n;for (int i = 1; i < n; i++) {int u, V;cin >> u >> V;if (u > V) swap(u, V);  // 统一标记规则m[ {u, V}] = 1; // 标记边 (u, v) 存在v[u].push_back(V);v[V].push_back(u);}// 二分图染色dfs(1, 0);// 找到所有颜色不同且没有直接连接的合法边for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {if (color[i] ^ color[j] && !m[ {i, j}]) {v2.push_back({i, j});  // 存储合法边}}}// 判断谁先手if (v2.size() % 2 == 0) {  // 如果合法边数是偶数，后手cout << "Second\n";} else {cout << "First\n" << v2[0].first << ' ' << v2[0].second << "\n";m[ {v2[0].first, v2[0].second}] = 1; // 标记已选择的边}int id2 = 0;while (1) {int u, v;cin >> u >> v;  // 读取高桥的选择if (u == -1 && v == -1) {return 0;  // 高桥选择退出，游戏结束}m[ {min(u, v), max(u, v)}] = 1; // 标记已选择的边// 跳过已选择的边，找到下一条合法边while (m[ {v2[id2].first, v2[id2].second}]) {id2++;}// 输出我的选择cout << v2[id2].first << ' ' << v2[id2].second << "\n";id2++;}return 0;
}