嗨,小蝴蝶。
今天我还能在『很久很久以前』的那一页上看到你吗?
泠珞给了你一棵大小为 n 的有标号有根树 T,T 中的结点从 1∼n 标号,其中标号为 Rt 的结点是它的根。
在最初的时候,T 的每个结点上写有一个 1∼n 之间的整数,称作这个结点的点权。保证 n 个结点的点权构成一个 1∼n 的排列。设标号为 i 的结点的点权是 ai,那么 a1∼an 构成一个 1∼n 的排列。
需要注意的是,对于 T 中的每个非叶子结点 u,u 的儿子 vi 之间都是有顺序的。设 u 有 k 个儿子,那么 u 的 k 个儿子从左到右依次称为 ch(u,1),ch(u,2),⋯⋯,ch(u,k)。
现在以 Rt 为根 DFS 这棵树 T。当访问到一个结点 u 的时候,我们按照 ch(u,1),ch(u,2),⋯⋯,ch(u,k) 的顺序,依次递归地 DFS 其未被访问过的 k 个儿子结点。这个过程将会得到唯一的一个 DFS 序列 s,其中 si 表示第 i 个被访问到的结点的标号是 si。
接下来你需要进行恰好 n−1 次删边操作,第 i 次操作将会删去 si+1 与 si+1 的父亲 Fa(si+1) 所连的边 (si+1,Fa(si+1))。
在第 i 次删边操作进行之前,你需要决定是否交换 si+1 的点权与 Fa(si+1) 的点权。如果你选择交换,那么 asi+1 与 aFa(si+1) 的值将会互换,然后 (si+1,Fa(si+1)) 将被删去;否则 (si+1,Fa(si+1)) 将被直接删去,不改变点权。
你一共需要做出 n−1 次选择,做出这 n−1 次选择的方案数共有 2n−1 种。 当 n−1 条边尽数被删去以后,设 a′i 表示最终标号为 i 的点的点权。我们定义集合 S 为所有通过交换操作可以得到的最终点权的排列构成的集合。换言之,一个 1∼n 的排列 p∈S 当且仅当存在至少一种做出选择的方案使得最终每个 a′i 都 =pi。
最后泠珞给了你一个 1∼n 的排列 p,你需要在下列三个小问中选择一个进行回答:
- 第 1 小问:判定 p 是否 ∈S。
- 第 2 小问:求出 p 在 S 中的后继。即求出字典序大于 p 并且 ∈S 的排列 q 中,字典序最小的那一个。如果 S 中存在字典序大于 p 的排列 q,你需要报告存在并输出字典序最小的那一个 q;否则你只需要报告不存在。
- 第 3 小问:求出 p 在 S 中的排名。即求出一共有多少个排列 q∈S,满足 q 的字典序小于 p,对大质数 998244353 取模。
输入格式
第一行两个整数 n,Rt,分别表示 T 的大小和 T 的根结点的标号。
第二行 n 个整数 a1,a2,⋯,an,依次表示初始时标号为 1,2,⋯,n 的结点的点权。
接下来 n 行,其中的第 i 行描述标号为 i 的结点:每行第一个整数 k 表示标号为 i 的结点的儿子个数。接下来 k 个整数 ch(i,1),ch(i,2),⋯⋯,ch(i,k),从左到右依次表示 i 的第 1,2,⋯,k 个儿子的标号。
最后一行 n 个整数 p1,p2,⋯,pn,表示泠珞给你的排列。
输出格式
本题使用 Special Judge。 你的输出必须包含恰好三行。其中:
- 第一行表示第 1 小问的答案,应该是一个大写字符串 YES 或者 NO;
- 第二行表示第 2 小问的答案,应该是 n 个 1∼n 之间的整数 q1,q2,⋯,qn,并且 q1,q2,⋯,qn 构成一个 1∼n 的排列;但是如果 S 中不存在字典序大于 p 的排列 q,你只需要输出一个整数 −1;
- 第三行表示第 3 小问的答案,应该是一个 [0,998244352] 之间的整数。
如果你不想回答三个小问中的某个或者某些,也可以在对应的行输出一个小写字符串 no comment,表示不想回答这个小问。忽略行末空格,但不忽略文末回车。在第三行之后应该恰有一个回车。
在一个测试点中:
- 如果你正确回答了第 1 小问,将获得该测试点满分 10% 的分数;
- 如果你正确回答了第 2 小问,无论第 1 小问是否回答、回答正确与否,都将获得该测试点满分 70% 的分数;
- 如果你正确回答了第 3 小问,无论第 1,2 小问是否回答、回答正确与否,都将获得该测试点满分 100% 的分数。
注意不符合输出格式的输出将直接获得 0 分!正确的回答、错误的回答以及 no comment 这三种输出都是符合输出格式的。 每个子任务的得分是该子任务中所有测试点得分的最小值。
样例 1
样例 1 输入
5 3 2 4 1 3 5 0 1 5 3 4 2 1 0 0 2 5 4 3 1
样例 1 输出
YES 3 4 2 1 5 9
样例 1 解释
以下按照字典序从小到大的顺序列出了 S 中的 16 个排列,每行一个排列:
1 5 2 3 4 2 1 4 3 5 2 3 4 1 5 2 4 1 3 5 2 4 3 1 5 2 5 1 3 4 2 5 3 1 4 2 5 4 1 3 2 5 4 3 1 3 4 2 1 5 3 5 2 1 4 4 1 2 3 5 4 3 2 1 5 4 5 2 1 3 4 5 2 3 1
附加样例 1~10
见下发文件。
保证第 1,2,⋯,10 个附加样例分别满足子任务 1,2,⋯,10 的限制。
子任务
对于所有数据,保证 2≤n≤2×105;n 个结点的儿子信息确实描述了一棵树 T;a1∼an,p1∼pn 均构成一个 1∼n 的排列。
以下是各子任务的具体情况以及特殊性质:
子任务编号 | 分值 | n= | 树的形态 | 特殊性质 | 子任务依赖 |
---|---|---|---|---|---|
1 | 5 | 20 | |||
2 | 5 | 8×104 | 完全二叉树 | DFS 序 1∼n | |
3 | 5 | 8×104 | 完全二叉树 | 2 | |
4 | 5 | 8×104 | 二叉树 | DFS 序 1∼n | 2 |
5 | 10 | 8×104 | 二叉树 | 2∼4 | |
6 | 10 | 8×104 | DFS 序 1∼n | 2,4 | |
7 | 15 | 8×104 | 1∼6 | ||
8 | 15 | 1.2×105 | 1∼7 | ||
9 | 15 | 1.6×105 | 1∼8 | ||
10 | 15 | 2×105 | 1∼9 |
- 『二叉树』:保证 T 中每个结点的儿子个数都 ≤2。
- 『完全二叉树』:保证 T 与一棵大小同样为 n 的完全二叉树同构,并且 Rt 对应完全二叉树的根。
- 『DFS 序 1∼n』:按照题目描述中所述方法对 T 进行 DFS,第 i 个被访问到的结点一定是标号为 i 的结点,即 si=i。