#P8499. [NOI2022] 挑战 NPC Ⅱ

[NOI2022] 挑战 NPC Ⅱ

题目描述

诸由杨是一名咸鱼大学生,虽然他每天仍然幻想着在多项式时间内解决 NPC 问题。

诸由杨上课的时候了解到子图同构问题是一个 NPC 问题。他打算给出一个子图同构问题的多项式判定算法,间接地去证明 P = NP,这样他一定可以凭借这个伟大的工作荣获图灵奖!只可惜诸由杨才疏学浅,连子图同构问题属于 NPC 的证明都没有想出来。因而他退而求其次,准备判定一个更加简单的问题:

给定两棵有根树 G,HG, H。设 G\lvert G \rvert 代表树 GG 中的节点个数,则这两棵树满足如下限制:$1 \leq \lvert H \rvert \leq \lvert G \rvert \leq \lvert H \rvert + k$。这里诸由杨保证 kk 是一个小常数。

诸由杨可以删除 GG 中的若干个节点,假定删除节点后后得到的子图为 GG'。他想要知道是否存在一种删除节点的方式,使得删除后得到的子图 GG' 满足如下条件:

  • GG' 连通。
  • GG' 包含 GG 中的根节点(也就是说 GG 根节点在删除过程中没有被删除)。
  • GG'HH 同构(也就是说存在一种让 GG' 中点重标号的方式,使得重标号得到的图和 HH 完全相同,且 GG 中的根节点经过重标号后恰好为 HH 的根节点)。

输入格式

本题有多组测试数据。

输入的第一行依次包含两个正整数 C,TC,T 和一个非负整数 kk,三个数字分别表示当前测试点编号,测试数据组数和题目中给定的常数。如果当前测试数据为样例则 C=0C = 0。保证 T500T \leq 500k5k \leq 5

对于每一组测试数据:

输入的第一行包含一个正整数 n1n_1,表示树 GG 中的节点个数,保证 1n11051 \leq n_1 \leq {10}^5,且 n15×105\sum n_1 \leq 5 \times {10}^5

输入的第二行包含 n1n_1 个整数,描述了树 GG 的结构。具体地,第 ii1in11 \leq i \leq n_1)个整数 aia_i 表示在树 GG 中节点 ii 的父节点,如果其为根节点则 ai=1a_i = -1。保证按照上述规则得到的树为连通有根树。

输入的第三行包含一个正整数 n2n_2,表示 HH 中的节点个数,保证对于所有测试数据,满足 max(1,n1k)n2n1\max(1, n_1 - k) \leq n_2 \leq n_1

输入的第四行包含 n2n_2 个整数,描述了树 HH 的结构。具体地,第 ii1in21 \leq i \leq n_2)个整数 bib_i 表示在树 HH 中节点 ii 的父节点,如果其为根节点则 bi=1b_i = -1。保证按照上述规则得到的树为连通有根树。

输出格式

对于每一组测试数据:

输出一行一个字符串。如果存在删除 GG 中节点的方式,使得其能够同时满足上述三个条件,则输出 Yes;否则输出 No

0 3 1
3
2 -1 2
2
-1 1
4
3 3 -1 3
3
2 3 -1
5
-1 1 5 5 1
5
2 3 -1 3 2

Yes
No
Yes

提示

【样例解释 #1】

对于第一个测试点,我们删除第一棵树的 11 号节点。此时剩余的树和输入第二棵树均为包含两个节点的有根树,因而输出为 Yes

对于第二个测试点,输入第一颗树深度为 11,但是输入第二颗树深度为 22。因而不论如何删除第一颗树的节点不会导致其树高增加到 22,因而输出为 No

对于第三个测试点,其输入两颗树均同构于下图的树,因而因而输出为 Yes


【样例 #2】

见附件中的 iso/iso2.iniso/iso2.ans

该样例数据范围满足测试点 787 \sim 8


【样例 #3】

见附件中的 iso/iso3.iniso/iso3.ans

该样例数据范围满足测试点 9109 \sim 10


【样例 #4】

见附件中的 iso/iso4.iniso/iso4.ans

该样例数据范围满足测试点 1313


【数据范围】

对于所有测试数据,满足 1T5001 \leq T \leq 5001n2n11051 \le n_2 \leq n_1 \le {10}^5n15×105\sum n_1 \leq 5 \times {10}^50k50 \leq k \leq 5。各测试点的附加限制如下表所示:

n1,n2n_1,n_2 n1\sum n_1 测试点 kk 特殊性质
8\leq 8 500\leq 500 131 \sim 3 0\leq 0
464 \sim 6 5\leq 5
16\leq 16 103\leq 10^3 787 \sim 8 0\leq 0
9109 \sim 10 5\leq 5
150\leq 150 104\leq 10^4 1111 0\leq 0
1212 1\leq 1
1313 5\leq 5
105\leq 10^5 5×105\leq 5 \times 10^5 141614 \sim 16 0\leq 0 A
172017 \sim 20 B
2121 1\leq 1
222322 \sim 23 3\leq 3
242524 \sim 25 5\leq 5

其中附加限制中的特殊性质如下所示:

  • 特殊性质 A:保证有根树 GG 每个节点要么是叶节点,要么有恰好 11 个儿子结点;另一种等价的表述是有根树 GG 构成了一条链,且根节点为链的一个端点。
  • 特殊性质 B:保证有根树 GG 每个节点要么是叶节点,要么有恰好 22 个儿子结点,同时保证 GG 的每一个叶节点深度均相同;另一种等价的表述是有根树 GG 构成一棵完全二叉树,且根节点为完全二叉树的根节点。

【提示】

数据没有针对任何合理的哈希算法做任何针对性的构造,所以在合理范围内不需要过度担心因为哈希碰撞而产生的失分问题。