| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 14 | 7 | 7 | 50.000% |
You are given a tree on $n$ nodes rooted at node 1ドル$. A spider and a fly are in the tree. The spider has three legs which are initially on nodes $a,ドル $b,ドル and $c$. The fly is on node $f$ and does not move.
Some nodes are considered to be in the shadow of the spider. A node is in the shadow of the spider if it lies on any of the three shortest paths between its legs, $a$--$b,ドル $a$--$c,ドル and $b$--$c$.
The spider can move its legs from vertices $a,ドル $b,ドル $c$ to vertices $a',ドル $b',ドル $c'$ if the size of its shadow remains constant and $\max\{\textrm{dist}(a, a'), \textrm{dist}(b, b'), \textrm{dist}(c, c')\}\leq 1$. The function $\textrm{dist}(u,,円v)$ indicates the number of edges on the shortest path between nodes $u$ and $v$ in the tree.
For example, here is one possible sequence of two moves by a spider with 6ドル$ nodes in its shadow. The vertices that have a red outline are in the shadow of the spider, and the vertices that are colored red are the spider's legs.
The spider eats through its legs. Determine whether the spider can move any of its legs to the fly's location, after any number of moves (possibly zero).
The first line of the input contains a single integer $t$ (1ドル\le t\le 10^4$) --- the number of test cases.
The first line of each test case contains a single integer $n$ (2ドル\leq n\leq 2\cdot 10^5$) --- the number of vertices in the tree.
The next line of each test case contains $n-1$ integers $p_2,,円p_3,,円\ldots,,円p_n$ (1ドル \le p_i < i$) --- the parents of each vertex in the tree, except the root.
The next line of each test case contains three integers $a,ドル $b,ドル and $c$ (1ドル\leq a,,円b,,円c\leq n$) --- the initial positions of each of the spider's legs.
The fourth and final line of each test case contains an integer $f$ (1ドル\leq f\leq n$) --- the position of the fly.
It is guaranteed that the sum of $n$ over all test cases does not exceed 2ドル\cdot 10^5$.
For each test case, print "YES" if the spider is able to catch the fly, and "NO" otherwise.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
7 2 1 2 2 2 1 6 1 1 3 1 5 2 4 5 1 6 1 1 3 1 5 2 4 6 1 18 1 2 3 2 5 3 1 7 7 7 4 2 12 4 12 4 15 12 15 12 16 12 1 1 3 4 5 5 7 4 9 10 9 1 6 11 12 12 1 1 3 4 5 5 7 4 9 10 9 1 6 11 4 12 1 1 3 4 5 5 7 4 9 10 9 1 6 11 6
Yes Yes No Yes Yes No Yes
In the first test case, all legs of the spider are initially on vertex 2ドル,ドル so that is the only vertex in the shadow. By moving all legs to vertex 1ドル$ at the same time, the spider can reach the food while keeping its shadow the same size.
In the second test case, the spider can use this move to reach the food with one of its legs:
In the third test case, the food is located at vertex 1ドル,ドル which is in the shadow of the spider, but the spider cannot move any of its legs to the food: