만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

배고픈 거미

시간 제한1초메모리 제한1024 MB

요약
나무에서 거미의 다리 세 개가 a, b, c에 있고 파리가 f에 있을 때, 그림자 크기를 유지하며 다리를 옮겨 파리의 위치에 닿을 수 있는지 판별합니다.
난이도

어려움10점 중 9점

유형
트리, DFS, 그리디
정답자
아직 제출이 없습니다

문제

트리가 주어지며, 루트는 정점 11이다. 트리는 nn개의 정점으로 이루어진다. 트리에는 거미와 파리가 있다. 거미에게는 다리가 세 개 있고, 처음에 다리는 정점 aa, bb, cc에 놓여 있다. 파리는 정점 ff에 있으며 움직이지 않는다.

정점이 거미의 그림자에 속한다는 것은, 그 정점이 다리끼리 이루는 세 최단 경로 aa-bb, aa-cc, bb-cc 중 하나에 놓인다는 뜻이다.

거미는 그림자의 크기가 그대로 유지되고 max⁡{dist(a,a′),dist(b,b′),dist(c,c′)}≤1\max\{\textrm{dist}(a, a'), \textrm{dist}(b, b'), \textrm{dist}(c, c')\}\leq 1을 만족하면, 다리를 aa, bb, cc에서 a′a', b′b', c′c'으로 옮길 수 있다. 여기서 dist(u,v)\textrm{dist}(u, v)는 트리에서 uu와 vv를 잇는 최단 경로의 간선 수이다.

예를 들어 아래 그림은 그림자 정점이 6개인 거미가 두 번 움직이는 한 가지 경우다. 그림자에 속한 정점은 빨간 테두리로, 다리가 놓인 정점은 빨간색으로 표시했다.

거미는 다리를 이용해 먹이를 먹는다. 거미가 임의의 횟수(0번도 가능)만큼 움직인 뒤 어느 다리든 파리의 위치로 옮길 수 있는지 판단하라.

입력

첫 줄에는 테스트 케이스의 수 tt (1≤t≤1041\le t\le 10^4)가 주어진다.

각 테스트 케이스의 첫 줄에는 트리의 정점 수 nn (2≤n≤2⋅1052\leq n\leq 2\cdot 10^5)이 주어진다.

다음 줄에는 루트를 제외한 각 정점의 부모 p2,p3,…,pnp_2, p_3, \ldots, p_n (1≤pi<i1 \le p_i < i)이 n−1n-1개 주어진다.

다음 줄에는 거미 다리의 처음 위치 aa, bb, cc (1≤a, b, c≤n1\leq a,\, b,\, c\leq n)가 주어진다.

마지막 줄에는 파리의 위치 ff (1≤f≤n1\leq f\leq n)가 주어진다.

모든 테스트 케이스의 nn 합은 2⋅1052\cdot 10^5를 넘지 않는다는 것이 보장된다.

출력

각 테스트 케이스마다 거미가 파리를 잡을 수 있으면 "YES", 아니면 "NO"를 출력한다. 대소문자는 구분하지 않으므로 "yEs", "yes", "Yes", "YES"는 모두 긍정으로 인정된다.

힌트

첫 번째 테스트 케이스에서는 거미의 모든 다리가 정점 22에 있으므로 그림자에 속한 정점은 22뿐이다. 모든 다리를 동시에 정점 11로 옮기면 그림자 크기를 유지한 채 먹이에 도달한다.

두 번째 테스트 케이스에서는 다음 움직임으로 다리 하나가 먹이에 도달한다.

세 번째 테스트 케이스에서는 먹이가 그림자에 속한 정점 11에 있지만, 거미는 어떤 다리로도 먹이에 도달할 수 없다.

예제1

  1. 예제 1

    입력
    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