#P6856. [2024年山东第二轮集训]树上排序
[2024年山东第二轮集训]树上排序
题目描述
给定一棵有 个节点的有根树,节点 上的整数为 ,且 是 的排列。目标是使每个节点 上的整数等于 。
必须按 的顺序进行 轮。第 轮选择节点 的子树中的一个节点 ,交换当前节点 与节点 上的整数。子树包含节点 自己,因此允许选择 。所有轮次结束后才检查最终排列。
判断是否可以完成目标,若可以,给出一组选择。
输入格式
第一行一个正整数 。每组输入三行。
- 一个正整数 。
- 个整数 。
- 个整数 ,其中 为节点 的父节点。根节点的父节点为 ,保证给出的是一棵树。根的编号不限。
输出格式
每组数据若无解,输出一行 NO。若有解,第一行输出 YES,第二行输出 个整数 ,第 个表示第 轮选中的节点。
评分方式
同一评测文件内,每组的 YES 或 NO 均正确且每组构造均正确,得满分。若可行性均判断正确但有构造不正确,则得 的分数。对于 YES,仍需在第二行输出恰好 个 范围内的整数。
样例
4
5
3 2 4 1 5
3 3 0 1 2
5
2 1 3 4 5
5 5 5 2 0
10
7 8 5 1 10 9 3 6 2 4
4 9 7 10 1 8 5 2 10 0
10
3 8 4 6 10 7 1 2 5 9
0 9 1 6 9 7 3 2 1 5
YES
4 2 4 4 5
NO
YES
5 6 3 1 3 6 3 6 2 4
YES
7 8 7 4 10 4 4 8 5 10
大样例见原题下发文件。
数据范围
,单个评测文件中所有组的 之和不超过 。,。原题时间限制 秒,内存限制 MB。
| 测试点 | 上界 | 附加限制 |
|---|---|---|
| 1–2 | 10 | |
| 3–5 | 500 | 互不相同 |
| 6–7 | ||
| 8–10 | 10000 | 互不相同 |
| 11–12 | ||
| 13–14 | ||
| 15–17 | 互不相同 | |
| 18–20 |