좋은 노드 집합 찾기

Alice와 Bob은 트리를 이용한 놀이를 즐겨한다. n개의 노드를 가진 트리 가 있고 노드는 편의상 번호가 1부터 n까지 붙어있다고 하자. i번 노드의 부모 노드는 p[i] 라 하고, 루트 노드의 경우 p[i] = 0 으로 정의한다. 마지막으로, 각 노드에는 정수 값이 부여되어있는데 이는 v[i]로 나타낸다.

예를 들어 위 그림 속의 트리는 n = 6, v = [30, 15, 10, 20, 15, 18] 이고 p = [0, 1, 1, 3, 3, 3]인 경우를 나타낸다. 각 노드 옆에 적힌 값이 노드에 부여된 정수 값이다. 이 트리의 경우 p[1] = 0 이므로 1이 루트 노드이고, 루트 노드를 제외한 모든 노드는 부모 노드를 갖는다.

이 트리의 임의의 노드 부분집합 S가 아래 조건을 만족하면 "좋은 노드 집합"이라 한다:

• 조건 1: 어떤 노드 x가 S에 속해있다면 x와 연결된 부모/자식 노드(들)은 S에 속하지 않는다.
• 조건 2: 자식 노드가 1개 이상인 어떤 노드 x가 S에 속하지 않았다면 x의 자식 노드(들)중 최소 하나의 노드는 S에 속한다.

예를 들어 위 트리에서 아래와 같은 노드 부분 집합을 살펴보자:

• S = {}: 조건 2를 만족하지 못하므로 좋은 모드 집합이 아니다. 가령 3번 노드가 S에 속하지 않았기 때문에 {4, 5, 6}중 최소 하나의 노드는 S에 속해야 한다.
• S = {3}: 두 조건을 모두 만족시키므로 좋은 노드 집합이다.
• S = {1, 2, 3}: 조건 2는 만족하지만 조건 1을 만족하지 않는다.
• S = {1, 4, 6}: 두 조건을 모두 만족시키므로 좋은 노드 집합이다.
• S = {2, 3}: 두 조건을 모두 만족시키므로 좋은 노드 집합이다.

노드 부분집합 S의 점수는 (Score(S)) S에 속한 노드들의 정수 값을 모두 더한 값으로 정의하자. 위 예제의 경우 S = {1, 4, 5, 6}일 때 30 + 20 + 15 + 18 = 83으로 가장 높은 점수를 달성할 수 있다 (아래 그림 참고).

입력으로 트리에 대한 정보가 주어졌을 때 Alice와 Bob이 달성할 수 있는 좋은 노드 집합의 가장 높은 점수를 구해보자.

입력 첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 노드의 수 n이 주어진다. 둘째 줄에는 각 노드에 부여된 정수 값이 주어지는데 (v[1], ..., v[n]), n개의 정수가 공백으로 구분되어 주어진다. 셋째 줄에는 각 노드의 부모 노드 번호가 주어지는데 (p[1], ..., p[n]), n개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다.

• 1 ≤ T ≤ 10

• 2 ≤ n ≤ 100,000

• -109 ≤ v[i] ≤ 109 (i = 1, 2, ..., n)

• 0 ≤ p[i] ≤ n (i = 1, 2, ..., n)

• 각 테스트 케이스에 대해:

  • i = 1, 2, ..., n중 단 하나의 i값에 대해서만 p[i] = 0 이다
  • 모든 i에 대하여 p[i] ≠ i 이다