#P6856. [2024年山东第二轮集训]树上排序

    ID: 6687 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-置换循环分解不变量分析SplayDFS 序子树转区间

[2024年山东第二轮集训]树上排序

题目描述

给定一棵有 nn 个节点的有根树,节点 ii 上的整数为 aia_i,且 aa 是 1,…,n1,\ldots,n 的排列。目标是使每个节点 ii 上的整数等于 ii。

必须按 i=1,…,ni=1,\ldots,n 的顺序进行 nn 轮。第 ii 轮选择节点 ii 的子树中的一个节点 xix_i,交换当前节点 ii 与节点 xix_i 上的整数。子树包含节点 ii 自己,因此允许选择 xi=ix_i=i。所有轮次结束后才检查最终排列。

判断是否可以完成目标,若可以,给出一组选择。

输入格式

第一行一个正整数 TT。每组输入三行。

  • 一个正整数 nn。
  • nn 个整数 a1,…,ana_1,\ldots,a_n。
  • nn 个整数 p1,…,pnp_1,\ldots,p_n,其中 pip_i 为节点 ii 的父节点。根节点的父节点为 00,保证给出的是一棵树。根的编号不限。

输出格式

每组数据若无解,输出一行 NO。若有解,第一行输出 YES,第二行输出 nn 个整数 x1,…,xnx_1,\ldots,x_n,第 ii 个表示第 ii 轮选中的节点。

评分方式

同一评测文件内,每组的 YES 或 NO 均正确且每组构造均正确,得满分。若可行性均判断正确但有构造不正确,则得 20%20\% 的分数。对于 YES,仍需在第二行输出恰好 nn 个 1,…,n1,\ldots,n 范围内的整数。

样例

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

大样例见原题下发文件。

数据范围

1≤n≤2×1051\le n\le2\times10^5,单个评测文件中所有组的 nn 之和不超过 5×1055\times10^5。1≤ai≤n1\le a_i\le n,0≤pi≤n0\le p_i\le n。原题时间限制 11 秒,内存限制 512512 MB。

测试点 ∑n\sum n 上界 附加限制
1–2 10
3–5 500 pip_i 互不相同
6–7
8–10 10000 pip_i 互不相同
11–12
13–14 5×1055\times10^5 pi<ip_i<i
15–17 pip_i 互不相同
18–20

原 PDF 题面