| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
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:
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 $n1$, representing the number of nodes in tree G, guaranteeing $1 \leq n1 \leq 10^5$, and $\sum n1 \leq 5 \times 10^5$. The second line of input contains $n1$ integers describing the structure of the tree $G$. Specifically, the i($1 \leq i \leq n1$)-th integer ai 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 $n2$, representing the number of nodes in $H$, which is guaranteed to satisfy $\max(1, n1 - k) \leq n2 \leq n1$ for all test data. The fourth line of input contains $n2$ integers describing the structure of the tree $H$. Specifically, the i($1 \leq i \leq n2$) 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.
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.
For all test data, $1 \leq T \leq 500$, $1 \le n2 \le n1 \le 10^5$, $\sum n1 \leq 5 \times 10^5$, $0 \leq k \leq 5$.
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
Yes No Yes
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.
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.