A16549. Rae Taylor and Trees (hard version)_编程练习题

题目描述

“竟然有平民敢想和我坐在一起。要认清你的身份！” —— Claire François 这是该问题的困难版本。困难版与简单版的区别在于，困难版要求你构造一个满足条件的树。 作为大地魔法师，Rae 精通种植树木的魔法！但 Manaria 吹嘘自己能种出更稀有的树。Rae 记得，最罕见的树可以用一个特定的排列来生成，请你帮她构造出来！ 给定一个长度为 $n$ 的排列 $p$。 请判断是否存在一棵有 $n$ 个结点（编号为 $1,2,\dots,n$）的无向树，满足如下条件： - 对于所有直接相连的一对结点 $u$、$v$（$1 \leq u < v \leq n$），$u$ 必须在排列 $p$ 中出现在 $v$ 前面。 如果存在，构造出任意一棵符合条件的树。 $^*$一个长度为 $n$ 的排列是一个恰好包含 $1$ 到 $n$ 每个整数各一次的序列，顺序任意。

第一行输入一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例组数。 每个测试用例第一行输入一个整数 $n$（$2 \leq n \leq 2 \times 10^5$）。 第二行输入 $n$ 个整数 $p_1,p_2,\dots,p_n$（$1 \leq p_i \leq n$）。保证所有 $p_i$ 两两不同。 保证所有测试用例中 $n$ 的总和不超过 $2\times 10^5$。

对于每个测试用例，如果存在满足条件的树，输出一行 “Yes”，否则输出 “No”。 如果答案是 “Yes”，接下来输出 $n-1$ 行，每行两个整数 $u\ v$，表示树中的一条边连接了 $u$ 和 $v$。 你可以用任意大写或小写方式输出答案单词。例如 "Yes", "yEs", "YES", "YeS" 均可被识别。

输入 #1

9
6
1 3 4 5 2 6
4
3 4 1 2
5
4 3 5 1 2
4
1 2 3 4
7
4 3 5 7 6 2 1
6
2 4 6 1 3 5
3
2 1 3
4
2 4 1 3
6
4 2 6 5 1 3

输出 #1

在第一个样例中，可以构造输出所给的树： - $1<3$，且 $1$ 在 $p$ 中比 $3$ 先出现， - $1<4$，且 $1$ 在 $p$ 中比 $4$ 先出现， - $5<6$，且 $5$ 在 $p$ 中比 $6$ 先出现， - $2<6$，且 $2$ 在 $p$ 中比 $6$ 先出现， - $1<6$，且 $1$ 在 $p$ 中比 $6$ 先出现。 在第二个样例中，可以证明不存在满足约束条件的树。