꽃

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

요약
뿌리로 갈수록 물 필요량이 줄어드는 화분 트리에서 두 사람이 번갈아 화분 하나나 그 부분 트리에 물을 주며, 최적으로 둘 때 승자를 구한다.
난이도

어려움10점 중 8점

유형
게임 이론, 트리, 그리디, 동적 계획법
정답자
아직 제출이 없습니다

문제

호시는 11번부터 NN번까지 NN개의 벽걸이 화분을 다음과 같이 설치했다. 먼저 11번 화분을 가장 높은 곳에 걸고, 22번부터 NN번까지 번호 순서대로 ii번 화분을 P_i<iP\_i < i인 P_iP\_i번 화분보다 낮게 걸어둔 다음 P_iP\_i번 화분으로부터 ii번 화분으로 위에서 아래로 흐르는 수도관을 연결해 주는 식으로 설치했다.

화분을 모두 설치한 다음, 호시는 모든 화분에 꽃을 하나씩 심었는데, ii번 화분에 심은 꽃은 매일 A_iA\_i만큼의 물이 필요하며 A_P_i≥A_iA\_{P\_{i}} \ge A\_{i}를 만족하도록 꽃을 심었다.

매일 모든 꽃에 정해진 양의 물을 주던 호시는 지루함을 느끼게 되었고, 친구 유키와 함께 다음과 같은 게임을 즐기기로 했다.

호시부터 시작하여 호시와 유키가 번갈아 가며 다음과 같은 규칙으로 화분에 물을 주게 된다.

  1. 11번 화분에 아직 A_1A\_1만큼의 물을 주지 않았다면 11번 화분을 고른다. 그렇지 않다면 2≤i≤N2 ≤ i ≤ N인 모든 ii에 대해 P_iP\_i번 화분에는 이미 A_P_iA\_{P\_i}만큼의 물을 주었고, ii번 화분에는 아직 A_iA\_i만큼의 물을 주지 않은 화분 중 원하는 화분을 하나 고른다.
  2. ii번 화분에 연결된 수도관을 전부 닫고 ii번 화분에 총 주어진 물이 A_iA\_i가 될 때까지 물을 준다. 혹은 ii번 화분을 포함해 ii번 화분에서 시작해 수도관을 통해 도달할 수 있는 모든 화분에 물을 11만큼 준다.

자신의 차례에 더 이상 화분에 물을 줄 수 없다면 게임에서 패배하게 된다.

둘 다 게임에서 이기기 위해 최선을 다한다고 할 때, 둘 중 누가 이길지 구해보자.

입력

첫 번째 줄에 테스트 케이스의 개수 TT가 주어진다. (1≤T≤1001\le T \le 100)

다음 줄부터 각 테스트 케이스의 정보가 주어진다. 하나의 테스트 케이스는 세 개의 줄로 이루어져 있으며, 첫 번째 줄에 벽걸이 화분의 개수 NN이 주어진다. (2≤N≤4002 \le N \le 400)

두 번째 줄에 P_2,P_3,…,P_NP\_2, P\_3, \dots, P\_N이 공백으로 구분되어 주어진다. (1≤P_i<i1 \le P\_i < i)

세 번째 줄에 A_1,A_2,…,A_NA\_1, A\_2, \dots, A\_N이 공백으로 구분되어 주어진다. (1≤A_i≤1091 \le A\_i \le 10^{9})

모든 테스트 케이스의 NN의 합은 400400을 넘지 않는다.

입력으로 주어지는 수는 모두 정수이다.

출력

각 테스트 케이스마다 호시가 이긴다면 First, 유키가 이긴다면 Second를 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    2
    3
    1 1
    5 3 3
    2
    1
    2 1
    
    예상 출력
    First
    Second