← 返回题目
题库练习 「NOI2022」挑战 NPC Ⅱ
← 上一题 下一题 →

A6722 | 「NOI2022」挑战 NPC Ⅱ

来源NOI
时间限制2s
内存限制1024MB
通过 / 提交0/0

题目描述

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

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

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

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

- $G'$ 连通。
- $G'$ 包含 $G$ 中的根节点（也就是说 $G$ 根节点在删除过程中没有被删除）。
- $G'$ 和 $H$ 同构（也就是说存在一种让 $G'$ 中点重标号的方式，使得重标号得到的图和 $H$ 完全相同，且 $G$ 中的根节点经过重标号后恰好为 $H$ 的根节点）。

输入格式

从文件 iso.in 中读入数据。

本题有多组测试数据。

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

对于每一组测试数据：

输入的第一行包含一个正整数 $n_1$，表示树 $G$ 中的节点个数，保证 $1 \leq n_1 \leq {10}^5$，且 $\sum n_1 \leq 5 \times {10}^5$。

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

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

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

输出格式

输出到文件 iso.out 中。

对于每一组测试数据：

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

输入输出样例

输入 #1
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
输出 #1
Yes
No
Yes
C++ 编辑器
输入
输出