4334 点的路径
时间限制2 S
内存限制128 MB
通过率85.7%(24 / 28)
题目描述
给你一棵由 n 个顶点组成的有根树。顶点从 1 到 n 编号。
树由包含 n 个数的数组 p 表示，其中第 i 个数表示 i 号点的父节点 pi ，根节点是唯一 pi = i 的点。
找到这样一组路径：
树由包含 n 个数的数组 p 表示，其中第 i 个数表示 i 号点的父节点 pi ，根节点是唯一 pi = i 的点。
找到这样一组路径：
- 每个顶点只属于一个路径，每个路径可以包含一个或多个顶点；
- 在每条路径中，每个下一个顶点——是当前顶点的子节点（即，路径总是向下——从父节点到子节点）；
- 要使得路径数量最少。
- 3 -> 1 -> 5
- 4
- 2
输入格式
输入数据的第一行包含一个整数 t (1 ≤ t ≤ 104) — 测试中的测试用例数。
每个测试用例由两行组成。
其中第一个包含整数 n (1 ≤ n ≤ 2⋅105)。 它是树中的顶点数。
第二行包含 n 个整数 p1, p2, … , pn (1 ≤ pi ≤ n)。 保证 p 数组是一个有根树。
保证测试中所有测试用例的 n 值之和不超过 2⋅105。
每个测试用例由两行组成。
其中第一个包含整数 n (1 ≤ n ≤ 2⋅105)。 它是树中的顶点数。
第二行包含 n 个整数 p1, p2, … , pn (1 ≤ pi ≤ n)。 保证 p 数组是一个有根树。
保证测试中所有测试用例的 n 值之和不超过 2⋅105。
输出格式
对于第一行的每个测试用例，输出一个整数 m 表示可以覆盖树的所有顶点的不相交的向下路径的最小数量。
然后打印 m 对包含路径描述的行。
首先输出路径的长度，在下一行中，按从上到下的顺序指定该路径的顶点序列。
您可以按任何顺序输出路径。 如果有多个答案，输出其中任何一个。
然后打印 m 对包含路径描述的行。
首先输出路径的长度，在下一行中，按从上到下的顺序指定该路径的顶点序列。
您可以按任何顺序输出路径。 如果有多个答案，输出其中任何一个。
输入输出样例
输入复制
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
输出复制
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来源