QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 1024 MB Total points: 100
[+7]

# 7764. 世界沉睡童话

Statistics

嗨,小蝴蝶。

今天我还能在『很久很久以前』的那一页上看到你吗?

泠珞给了你一棵大小为 n 的有标号有根树 TT 中的结点从 1n 标号,其中标号为 Rt 的结点是它的根。

在最初的时候,T 的每个结点上写有一个 1n 之间的整数,称作这个结点的点权。保证 n 个结点的点权构成一个 1n 的排列。设标号为 i 的结点的点权是 ai,那么 a1an 构成一个 1n 的排列。

需要注意的是,对于 T 中的每个非叶子结点 uu 的儿子 vi 之间都是有顺序的。设 uk 个儿子,那么 uk 个儿子从左到右依次称为 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

接下来你需要进行恰好 n1 次删边操作,第 i 次操作将会删去 si+1si+1 的父亲 Fa(si+1) 所连的边 (si+1,Fa(si+1))

在第 i 次删边操作进行之前,你需要决定是否交换 si+1 的点权与 Fa(si+1) 的点权。如果你选择交换,那么 asi+1aFa(si+1) 的值将会互换,然后 (si+1,Fa(si+1)) 将被删去;否则 (si+1,Fa(si+1)) 将被直接删去,不改变点权。

你一共需要做出 n1 次选择,做出这 n1 次选择的方案数共有 2n1 种。 当 n1 条边尽数被删去以后,设 ai 表示最终标号为 i 的点的点权。我们定义集合 S 为所有通过交换操作可以得到的最终点权的排列构成的集合。换言之,一个 1n 的排列 pS 当且仅当存在至少一种做出选择的方案使得最终每个 ai=pi

最后泠珞给了你一个 1n 的排列 p,你需要在下列三个小问中选择一个进行回答:

  • 1 小问:判定 p 是否 S
  • 2 小问:求出 pS 中的后继。即求出字典序大于 p 并且 S 的排列 q 中,字典序最小的那一个。如果 S 中存在字典序大于 p 的排列 q,你需要报告存在并输出字典序最小的那一个 q;否则你只需要报告不存在。
  • 3 小问:求出 pS 中的排名。即求出一共有多少个排列 qS,满足 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 小问的答案,应该是 n1n 之间的整数 q1,q2,,qn,并且 q1,q2,,qn 构成一个 1n 的排列;但是如果 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 的限制。

子任务

对于所有数据,保证 2n2×105n 个结点的儿子信息确实描述了一棵树 Ta1anp1pn 均构成一个 1n 的排列。

以下是各子任务的具体情况以及特殊性质:

子任务编号分值n=树的形态特殊性质子任务依赖
1520
258×104完全二叉树DFS 序 1n
358×104完全二叉树2
458×104二叉树DFS 序 1n2
5108×104二叉树24
6108×104DFS 序 1n2,4
7158×10416
8151.2×10517
9151.6×10518
10152×10519
  • 『二叉树』:保证 T 中每个结点的儿子个数都 2
  • 『完全二叉树』:保证 T 与一棵大小同样为 n 的完全二叉树同构,并且 Rt 对应完全二叉树的根。
  • 『DFS 序 1n』:按照题目描述中所述方法对 T 进行 DFS,第 i 个被访问到的结点一定是标号为 i 的结点,即 si=i