NOI '22 P4 - Challenge NPC

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem type

Given two rooted trees G, H. Let |G| represent the number of nodes in tree G, then the two trees satisfy the following constraints: 1 \le |H| \le |G| \le |H| + k. It guarantees that k is a small constant. You can delete several nodes in G, assuming that the subgraph obtained after deleting the nodes is G'. He wants to know if there is a way to delete nodes such that the subgraph G' obtained after deletion satisfies the following conditions:

  • G' is connected.
  • G' contains the root node in G (that is, the G root node is not deleted during deletion).
  • G' and H are isomorphic (that is, there is a way to relabel the points in G', so that the graph obtained by relabeling is exactly the same as H, and the root node in G is exactly the root of H after relabeling the nodes).

Input format

There are multiple sets of test data for this question. The first line of input contains two positive integers C, T and a non-negative integer k. The three numbers represent the current test point number, the number of test data groups and the constant given in the question. C = 0 if the current test data is a sample. It is guaranteed that T \leq 500, k \leq 5.

For each set of test data: The first line of input contains a positive integer n_1, representing the number of nodes in tree G, guaranteeing 1 \leq n_1 \leq 10^5, and \sum n_1 \leq 5 \times 10^5. The second line of input contains n_1 integers describing the structure of the tree G. Specifically, the i (1 \leq i \leq n_1)-th integer a_i represents the parent node of node i in tree G, and if it is the root node, a_i = -1. It is guaranteed that the tree obtained according to the above rules is a connected rooted tree. The third line of input contains a positive integer n_2, representing the number of nodes in H, which is guaranteed to satisfy \max(1, n_1 - k) \leq n_2 \leq n_1 for all test data. The fourth line of input contains n_2 integers describing the structure of the tree H. Specifically, the i (1 \leq i \leq n_2) integer b_i represents the parent node of node i in tree H, and if it is the root node, b_i = -1. It is guaranteed that the tree obtained according to the above rules is a connected rooted tree.

Output format

For each set of test data: Output one string per line. If there is a way to delete the node in G so that it can satisfy the above three conditions at the same time, output Yes; otherwise, output No.

Samples

Sample inputs and outputs can be found here.

Sample Input 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

Sample Output 1

Yes
No
Yes

Explanation of Sample 1

For the first test point, we delete node 1 of the first tree. At this point the remaining tree and the input second tree are both rooted trees with two nodes, so the output is Yes.

For the second test point, enter a depth of 1 for the first tree, but a depth of 2 for the second tree. Therefore, deleting the node of the first tree will not cause its tree height to increase to 2, so the output is No.

For the third test point, the input two trees are isomorphic to the tree in the figure below, so the output is Yes.

Sample 2

See iso/iso2.in and iso/iso2.ans in the player directory. The sample data range satisfies test points 7 ∼ 8

Sample 3

See iso/iso3.in and iso/iso3.ans in the player directory. The sample data range satisfies test points 9 ∼ 10.

Sample 4

See iso/iso4.in and iso/iso4.ans in the player directory. The sample data range meets test point 13.

Subtasks

For all test data, 1 \leq T \leq 500, 1 \le n_2 \le n_1 \le 10^5, \sum n_1 \leq 5 \times 10^5, 0 \leq k \leq 5. Additional restrictions for each test point are shown in the table below:

n_1, n_2\sum n_1CasekSpecial Property
\leq 8\leq 5001,2,30None
4, 5, 6\leq 5
\leq 16\leq 10^37, 80
9, 10\leq 5
\leq 150\leq 10^4110
12\leq 1
13\leq 5
\leq 10^5\leq 5 \times 10^514, 15, 160A
17, 18, 19, 20B
21\leq 1None
22, 23\leq 3
24, 25\leq 5

The special properties among the additional restrictions are as follows:

  • Special property A: It is guaranteed that each node of the rooted tree G is either a leaf node or has exactly 1 child node; another equivalent expression is that the rooted tree G constitutes a chain, and the root node is a chain an endpoint.
  • Special property B: It is guaranteed that each node of the rooted tree G is either a leaf node or has exactly 2 child nodes, and each leaf node of G is guaranteed to have the same depth; another equivalent expression is a rooted tree G constitutes a complete binary tree, and the root node is the root node of the complete binary tree

Hint

The data does not have any targeted structure for any reasonable hash algorithm, so within a reasonable range, there is no need to worry too much about the loss of points due to hash collisions.


Comments

There are no comments at the moment.