P8499 [NOI2022] Challenge NPC II

Zhu Youyang is a laid-back college student, but he still dreams every day of solving NPC problems in polynomial time. In class, Zhu Youyang learned that the subgraph isomorphism problem is an NPC problem. He plans to give a polynomial-time decision algorithm for subgraph isomorphism, and indirectly prove that $P = NP$. Then he will surely win the Turing Award with this great work! Unfortunately, Zhu Youyang is not knowledgeable enough, and he cannot even come up with a proof that subgraph isomorphism is NPC. Therefore, he steps back and decides to solve a simpler problem: Given two rooted trees $G, H$. Let $\lvert G \rvert$ denote the number of nodes in tree $G$. The two trees satisfy the following constraint: $1 \leq \lvert H \rvert \leq \lvert G \rvert \leq \lvert H \rvert + k$. Here Zhu Youyang guarantees that $k$ is a small constant. Zhu Youyang may delete some nodes in $G$, and let the subgraph obtained after deletion be $G'$. He wants to know whether there exists a way to delete nodes such that the resulting subgraph $G'$ satisfies: - $G'$ is connected. - $G'$ contains the root of $G$ (that is, the root of $G$ is not deleted during the deletion process). - $G'$ is isomorphic to $H$ (that is, there exists a way to relabel the nodes of $G'$ such that the relabeled graph is exactly the same as $H$, and the root of $G$ becomes exactly the root of $H$ after relabeling).

This problem contains multiple test cases. The first line of input contains two positive integers $C, T$ and a non-negative integer $k$. These three numbers represent the current subtask index, the number of test cases, and the constant given in the statement. If the current testdata is a sample, then $C = 0$. It is guaranteed that $T \leq 500$ and $k \leq 5$. For each test case: The first line contains a positive integer $n_1$, the number of nodes in tree $G$. It is guaranteed that $1 \leq n_1 \leq {10}^5$, and $\sum n_1 \leq 5 \times {10}^5$. The second line contains $n_1$ integers describing the structure of tree $G$. Specifically, the $i$-th integer ($1 \leq i \leq n_1$) $a_i$ indicates the parent of node $i$ in tree $G$. If it is the root, then $a_i = -1$. It is guaranteed that the tree obtained by the above rule is a connected rooted tree. The third line contains a positive integer $n_2$, the number of nodes in $H$. It is guaranteed that for all testdata, $\max(1, n_1 - k) \leq n_2 \leq n_1$. The fourth line contains $n_2$ integers describing the structure of tree $H$. Specifically, the $i$-th integer ($1 \leq i \leq n_2$) $b_i$ indicates the parent of node $i$ in tree $H$. If it is the root, then $b_i = -1$. It is guaranteed that the tree obtained by the above rule is a connected rooted tree.

For each test case: Output one line containing a string. If there exists a way to delete nodes from $G$ such that all three conditions above are satisfied, output `Yes`; otherwise output `No`.

**Sample Explanation \#1** For the first test point, we delete node $1$ of the first tree. Then the remaining tree and the second input tree are both rooted trees with two nodes, so the output is `Yes`.  For the second test point, the depth of the first input tree is $1$, but the depth of the second input tree is $2$. Therefore, no matter how we delete nodes from the first tree, its height cannot increase to $2$, so the output is `No`.  For the third test point, the two input trees are both isomorphic to the tree shown below, so the output is `Yes`.  ---- **Sample \#2** See `iso/iso2.in` and `iso/iso2.ans` in the attachments. The constraints of this sample satisfy test points $7 \sim 8$. ---- **Sample \#3** See `iso/iso3.in` and `iso/iso3.ans` in the attachments. The constraints of this sample satisfy test points $9 \sim 10$. ---- **Sample \#4** See `iso/iso4.in` and `iso/iso4.ans` in the attachments. The constraints of this sample satisfy test point $13$. ---- **Constraints** For all testdata, it holds that $1 \leq T \leq 500$, $1 \le n_2 \leq n_1 \le {10}^5$, $\sum n_1 \leq 5 \times {10}^5$, $0 \leq k \leq 5$. The additional constraints for each test point are shown in the table below: | $n_1,n_2$ | $\sum n_1$ | Test Points | $k$ | Special Property | |:-----------:|:--------------------:|:---------------------:|:--------:|:------------------------:| | $\leq 8$ | $\leq 500$ | $1 \sim 3$ | $\leq 0$ | None | | $\leq 8$ | $\leq 500$ | $4 \sim 6$ | $\leq 5$ | None | | $\leq 16$ | $\leq 10^3$ | $7 \sim 8$ | $\leq 0$ | None | | $\leq 16$ | $\leq 10^3$ | $9 \sim 10$ | $\leq 5$ | None | | $\leq 150$ | $\leq 10^4$ | $11$ | $\leq 0$ | None | | $\leq 150$ | $\leq 10^4$ | $12$ | $\leq 1$ | None | | $\leq 150$ | $\leq 10^4$ | $13$ | $\leq 5$ | None | | $\leq 10^5$ | $\leq 5 \times 10^5$ | $14 \sim 16$ | $\leq 0$ | A | | $\leq 10^5$ | $\leq 5 \times 10^5$ | $17 \sim 20$ | $\leq 0$ | B | | $\leq 10^5$ | $\leq 5 \times 10^5$ | $21$ | $\leq 1$ | None | | $\leq 10^5$ | $\leq 5 \times 10^5$ | $22 \sim 23$ | $\leq 3$ | None | | $\leq 10^5$ | $\leq 5 \times 10^5$ | $24 \sim 25$ | $\leq 5$ | None | The special properties in the additional constraints are as follows: - Special Property A: It is guaranteed that in rooted tree $G$, every node is either a leaf or has exactly $1$ child. An equivalent statement is that rooted tree $G$ forms a chain, and the root is one endpoint of the chain. - Special Property B: It is guaranteed that in rooted tree $G$, every node is either a leaf or has exactly $2$ children, and all leaves of $G$ have the same depth. An equivalent statement is that rooted tree $G$ is a perfect binary tree, and the root is the root of that perfect binary tree. **Hint** The testdata has **not been constructed to target any reasonable hashing algorithm**, so within a reasonable range there is no need to worry too much about losing points due to hash collisions. Translated by ChatGPT 5