시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 12 3 3 60.000%

문제

'주식회사 월드'의 조직도는 루트가 있는 트리 형태의 구조를 가지고 있다. 즉, 사장님을 트리의 루트로 하며, 직원들은 자신의 직속상관 바로 밑에 매달려 있는 형태가 된다.

김진영 부사장은 2008년 설을 맞아 '주식회사 월드'의 신년 파티를 계획 중에 있다. 단, 만일 부하직원이 자신의 직속상관과 파티에 함께 오게 되면 분위기가 경직될 수 있으므로, 파티의 분위기를 위해 부하직원과 그 직속상관은 같이 초대될 수 없도록 하려고 한다.

예를 들어 최백준 과장이 오민식, 오영식 대리의 직속상관이라고 하자, 만일 최백준 과장을 파티에 초대하려 한다면 오민식, 오영식 두 대리는 파티에 초대할 수 없다. 마찬가지로 오민식, 오영식 대리 중 어느 한 명이라도 파티에 초대하려 한다면 최백준 과장 역시 파티에 초대될 수 없다.

각 직원들의 "날라리 기질"은 평소 인사과의 관찰을 통해 회사의 데이터베이스에 기록이 되어 있다고 한다. 신년 파티의 "날라리 분위기"란 파티 참가자들의 "날라리 기질"의 합으로 정해진다.

김진영 부사장은 위의 제한을 만족시키면서 이번 신년 파티의 "날라리 분위기"를 최대화하도록 참가자 목록을 작성하려고 한다. 단, 사장의 참석 여부가 아직 불투명한 상황이기 때문에 사장이 참석하는 경우와 그렇지 않은 경우 각각에 대해 모두 참가자 목록을 결정해 줄 프로그램을 작성해야 한다. 아무도 초대하지 않는 경우 "날라리 분위기"가 최대일 수도 있다는 점에 주의한다.

입력

첫째 줄에 사장을 포함한 모든 직원의 수 N이 주어진다. (2≤N≤200,000) 사장은 1번이며, 다른 직원들은 2번부터 N번까지 차례로 번호가 매겨져 있다. 둘째 줄에는 사장을 포함한 모든 직원의 "날라리 기질"을 나타내는 N개의 정수가 빈 칸을 사이에 두고 1번 직원(사장)부터 N번 직원까지 순서대로 주어진다. 주어지는 정수는 절대값이 10,000을 넘지 않는다. 셋째 줄에는 사장을 제외한 모든 직원의 직속 상관의 번호를 나타내는 N-1개의 정수가 빈 칸을 사이에 두고 2번 직원부터 N번 직원까지 순서대로 주어진다. 주어지는 수는 물론 N 이하의 자연수이며, 항상 루트가 있는 트리 형태의 구조를 갖도록 입력이 주어진다고 가정해도 좋다.

출력

첫째 줄에는 사장이 참석하는 경우와 그렇지 않은 경우의  "날라리 분위기"의 최대값을 빈 칸을 사이에 두고 순서대로 출력한다. 둘째 줄과 셋째 줄에는 각각 사장이 참석하는 경우와 그렇지 않은 경우의 참가자 번호를 빈 칸을 사이에 두고 증가하는 순서대로 출력한다. 각 줄의 끝에는 -1을 추가로 출력해서 끝을 표시하도록 한다.

예제 입력

6
-10 5 20 15 -5 10
1 1 2 2 1

예제 출력

5 45
1 4 -1
3 4 6 -1

힌트

출처

  • 문제를 번역한 사람: author5