====== 교육적인 트리 문제 ======

===== 풀이 =====
  * 어떤 노드를 선택하기 위해, 자신의 부모 또한 선택되어 있어야 한다는 조건은 의미가 없다. 부모 노드가 자식노드 보다 더 큰 값을 갖도록 주어져있기 때문에, 큰 노드 부터 선택하면 당연히 부모노드가 먼저 선택된다.
  * 그렇다면, 그냥 조건을 신경쓰지 말고, 가장 큰 노드부터 차례대로 뽑으면 된다. 저 조건을 무시하면 트리 구조를 신경 쓸 필요도 없다. 그냥 값들을 정렬하고 누적합을 출력하면 끝이다. 시간복잡도는 정렬에 드는 O(nlogn)이다.
  * 이것만으로는 왜 문제 제목에 '교육적인'이라는 단어가 붙어있는지 모르겠다; 낚시인가..
  * 굳이 좀더 생각해보면, 사실 원래 이렇게 자식노드가 부모노드보다 작다는 특수한 성질을 만족하는 트리에서 최댓값 K개를 뽑는 데에 사용되는 [[ps:tutorial:fracturing search]]라는 기법이 있기는 하다. 만약 뽑아야 하는 최댓값이 K<<N개 이고, 트리의 차수가 제한되어 있는 상황이라면, 저 방식을 써서 O(klogk)에 풀 수도 있을 것이다. (어차피 전처리에 O(n)이 들어갈거라서 실제 속도로는 그래도 별 차이 없을수도 있을것 같지만..)


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 30108. 교육적인 트리 문제".

- Problem link: https://www.acmicpc.net/problem/30108
- Solution link: http://www.teferi.net/ps/problems/boj/30108
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    p = [int(x) - 1 for x in input().split()]  # pylint: disable=unused-variable
    a = [int(x) for x in input().split()]

    answer = 0
    for num in sorted(a, reverse=True):
        answer += num
        print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}