| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 355 | 108 | 72 | 31.169% |
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가 아래 조건을 만족하면 "좋은 노드 집합"이라 한다:
예를 들어 위 트리에서 아래와 같은 노드 부분 집합을 살펴보자:
노드 부분집합 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개의 정수가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
5 6 30 15 10 20 15 18 0 1 1 3 3 3 6 1 120 100 10 20 30 0 1 1 3 3 3 6 100 8 5 -20 -30 15 0 1 1 3 3 3 5 -1 -2 -3 -4 -5 2 3 4 5 0 2 -2022 2022 0 1
83 220 115 -6 2022
예제 1: 본문에서 다루었다.
예제 2: 본문의 예제와 같은 구조의 트리이지만 각 노드에 부여된 정수 값이 다르다.
이 경우 S = {2, 3}이 점수를 최대로 하는 좋은 노드 부분집합이다.
예제 3: 추가 설명 없음.
예제 4: 아래 그림은 입력으로 주어진 트리를 나타낸다. S = {4, 2}가 점수를 최대로 하는 좋은 노드 부분집합이다.
예제 5: 추가 설명 없음.