← 返回题目列表

Codeforces · 1675/D

D. 垂直路径

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 个顶点组成的有根树。顶点编号从 $$$1$$$ 到 $$$n$$$。任何顶点都可以是树的根。

树是无环的连通无向图。有根树是具有选定顶点(称为根)的树。

树由包含 $$$n$$$ 数字的父节点 $$$p$$$ 数组指定:$$$p_i$$$ 是索引为 $$$i$$$ 的顶点的父节点。顶点 $$$u$$$ 的父顶点是从 $$$u$$$ 到根的最短路径上的下一个顶点。例如,在从 $$$5$$$ 到 $$$3$$$ (根)的简单路径上,下一个顶点将是 $$$1$$$,因此 $$$5$$$ 的父节点是 $$$1$$$。

根没有父节点,因此对于它来说,$$$p_i$$$ 的值为 $$$i$$$ (根是 $$$p_i=i$$$ 的唯一顶点)。

找到这样一组路径:

- 每个顶点都属于一条路径,每个路径可以包含一个或多个顶点;
- 在每条路径中,每个下一个顶点 - 是当前顶点的子节点(也就是说,路径总是向下引导 - 从父节点到子节点);
- 路径数量最少。

例如,如果 $$$n=5$$$ 且 $$$p=[3, 1, 3, 3, 1]$$$,则树可以分为三个路径:

1. $$$3 \rightarrow 1 \rightarrow 5$$$ ($$$3$$$ 顶点的路径),
2. $$$4$$$($$$1$$$ 顶点的路径)。
3. $$$2$$$($$$1$$$ 顶点的路径)。

将根树拆分为 $$$n=5$$$ 的三个路径的示例,树的根 — 节点 $$$3$$$。

输入

输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。

每个测试用例由两行组成。

第一个包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。它是树中顶点的数量。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$)。保证 $$$p$$$ 数组编码一些有根树。

保证测试中所有测试用例的值 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于第一行的每个测试用例,输出一个整数 $$$m$$$ — 可以覆盖树的所有顶点的非相交引导路径的最小数量。

然后打印 $$$m$$$ 包含路径描述的行。在第一个中打印路径的长度,在第二个中打印从上到下的顺序指定该路径的顶点序列。您可以按任何顺序输出路径。

如果有多个答案,则输出其中任何一个。

示例

输入 #1

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

输出 #1

3
3
3 1 5
1
2
1
4

2
2
1 2
2
4 3

1
7
1 2 3 4 5 6 7

1
1
1

3
3
4 1 5
2
2 6
1
3

3
2
2 1
1
3
1
4