The 67th Tree Problem
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem Description
既然 PMOI 赛季已经结束(Cloud 获胜),Macaque 可以继续他的悟道之旅。他要解决的问题越来越难,前世的重担越来越沉,而你正在以如此快的速度丧失自由意志,以至于你很难记起上一次出于自己意愿而非被 Macaque 强迫去做任何事情是什么时候。对你来说唯一的好处是,一旦你为他解决了以下问题,Macaque 将带你免费参观他目前在树上栖息的地方。
给定两个整数 $x$ 和 $y$。
你的任务是构造一棵有 $x + y$ 个节点的树,以节点 $1$ 为根,满足:
- 恰好有 $x$ 个节点的子树$^{\text{∗}}$ 大小为偶数。
- 恰好有 $y$ 个节点的子树大小为奇数。
$^{\text{∗}}$顶点 $u$ 的子树是指所有在到根节点的简单路径上经过 $u$ 的顶点的集合(包括 $u$ 本身)。
Input Format
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$($1 \le t \le 10^4$)。接下来是每个测试用例的描述。
接下来的每一行包含两个整数 $x$ 和 $y$($0 \leq x, y \leq 2 \cdot 10^5$,$1 \leq x + y \leq 2 \cdot 10^5$)。
保证所有测试用例的 $x+y$ 之和不超过 $2\cdot 10^5$。
Output Format
对于每个查询,输出 "YES" 或 "NO",取决于是否存在合法的构造。你可以以任意大小写形式输出 "YES" 和 "NO"(例如,"yES"、"yes" 和 "Yes" 都会被识别为肯定回答)。
如果你输出 "YES",则输出 $x+y-1$ 行,每行包含两个以空格分隔的整数 $u$ 和 $v$,表示节点 $u$ 和节点 $v$ 之间有一条边。
Examples
7
1 1
2 1
0 3
3 4
0 2
1 0
4 7
YES
1 2
NO
YES
1 2
1 3
YES
1 2
2 3
3 4
4 5
5 6
6 7
NO
NO
YES
1 2
2 3
3 4
4 5
4 11
2 6
6 7
7 8
2 9
9 10
Note
在第一个测试中,输出的树是合法的,因为节点 $1$ 的子树大小为 $2$,是偶数;节点 $2$ 的子树大小为 $1$,是奇数。
在第二个测试中,可以证明不存在合法的树。
在第四个测试中,子树大小为偶数的节点是 $[2, 4, 6]$,子树大小为奇数的节点是 $[1, 3, 5, 7]$。
最后一个测试的输出如下图所示,其中蓝色节点的子树大小为偶数,红色节点的子树大小为奇数。
Source
Imported from Codeforces — Codeforces Round 1090 (Div. 4).
Codeforces Round 1090 (Div. 4)
- 状态
- 已结束
- 规则
- XCPC
- 题目
- 7
- 开始于
- 2026-11-11 15:00
- 结束于
- 2026-11-11 17:30
- 持续时间
- 2.5 小时
- 主持人
- 参赛人数
- 14