신년 파티
면접 대비시간 제한2초메모리 제한128 MB
조직도가 트리 구조인 회사에서 직속 상사와 부하가 동시에 초대되지 않도록 하면서, 사장 참석과 불참 두 경우 각각 흥미도 총합이 최대인 초대 명단을 구합니다.
문제
어떤 회사의 조직도는 사장을 루트로 하는 트리 구조이다. 사장을 제외한 모든 직원은 정확히 한 명의 직속 상관을 가지며, 그 직원은 조직도에서 직속 상관의 바로 아래에 놓인다.
부사장은 설을 맞아 신년 파티를 준비하고 있다. 파티 분위기가 어색해지는 일을 막기 위해, 어떤 직원과 그 직원의 직속 상관을 동시에 초대할 수 없다.
각 직원에게는 평소 관찰을 통해 정해진 흥겨움 점수가 있다. 파티의 전체 흥겨움은 초대된 직원들의 흥겨움 점수 합으로 정해진다.
위 조건을 만족하면서 전체 흥겨움을 최대화하는 참가자 목록을 구해야 한다. 단, 사장이 참석하는 경우와 사장이 참석하지 않는 경우를 각각 따로 계산해야 한다. 점수가 음수일 수 있으므로, 사장이 참석하지 않는 경우에는 아무도 초대하지 않는 것이 최적일 수도 있다.
입력
첫째 줄에 사장을 포함한 직원 수 N이 주어진다. 2 <= N <= 200,000이다. 사장은 1번이며, 나머지 직원은 2번부터 N번까지 번호가 붙어 있다.
둘째 줄에는 1번 직원부터 N번 직원까지의 흥겨움 점수를 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 정수의 절댓값은 10,000 이하이다.
셋째 줄에는 2번 직원부터 N번 직원까지, 각 직원의 직속 상관 번호 N-1개가 공백으로 구분되어 주어진다. 입력은 항상 1번을 루트로 하는 올바른 트리를 이룬다.
출력
첫째 줄에 사장이 참석하는 경우의 최대 흥겨움과 사장이 참석하지 않는 경우의 최대 흥겨움을 이 순서대로 공백으로 구분해 출력한다.
둘째 줄에는 사장이 참석하는 경우 초대할 직원 번호를 증가하는 순서로 출력하고, 줄 끝에 -1을 추가로 출력한다.
셋째 줄에는 사장이 참석하지 않는 경우 초대할 직원 번호를 증가하는 순서로 출력하고, 줄 끝에 -1을 추가로 출력한다.