만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

인사 평가

시간 제한2초메모리 제한512 MB

요약
각 직원에 대해, 자기보다 기술 등급이 낮은 모든 부하 직원 j의 t_j 합을 구한다.
난이도

보통10점 중 7점

유형
트리, DFS, 세그먼트 트리, 누적 합
정답자
아직 제출이 없습니다

문제

어떤 회사 엔지니어링 부문에서는 이사를 제외한 모든 직원이 관리자 한 명에게 보고하고, 모든 직원은 직접 또는 여러 단계를 거쳐 이사에게 보고한다. 마리아는 이 부문의 인사 평가 제도를 맡고 있다. 관리자가 직속 부하 직원을 평가하던 방식이 잘 돌아가지 않았기 때문에, 마리아는 직원마다 기술 등급을 하나씩 매기는 새 제도를 만들었다.

새 제도에서 직원은 자기보다 기술 등급이 낮은 부하 직원만 평가한다. 직원 ii의 부하 직원은 ii에게 직접 보고하는 직원과, 관리자 사슬을 거쳐 ii에게 보고하는 직원을 모두 말한다. 직원 jj는 최근에 한 일을 정리하고, 그 정리본을 한 번 검토하는 데 걸리는 시간 tjt_j를 산정한다. jj의 상급자 중 기술 등급이 rjr_j보다 높은 사람은 모두 tjt_j만큼 시간을 써서 jj의 평가를 작성한다. 기술 등급이 같은 상급자는 평가를 쓰지 않는다.

마리아는 이 제도가 만드는 업무량을 알고 싶다. 부문의 조직 구조가 주어질 때, 직원마다 평가를 쓰는 데 드는 총 시간을 구하라.

입력

첫 줄에 직원 수 EE가 주어진다. 직원 번호는 1부터 EE까지이다. 다음 EE개의 줄에는 직원 1번부터 직원 EE번까지의 정보가 차례로 주어진다. ii번째 줄에는 세 정수 mim_i, rir_i, tit_i가 공백으로 구분되어 주어지며, 각각 직원 ii의 관리자 번호, 기술 등급, 검토 한 번에 걸리는 예상 시간이다. 이사는 관리자가 없으므로 mi=−1m_i = -1로 주어진다. 나머지 직원의 mim_i는 1 이상 EE 이하이다.

출력

EE개의 줄을 출력한다. ii번째 줄에는 직원 ii가 평가를 쓰는 데 쓰는 총 시간을 출력한다.

제한

  • 1≤E≤1000001 \le E \le 100000, 직원 수
  • 1≤ri≤1000001 \le r_i \le 100000, 각 직원의 기술 등급
  • 1≤ti≤1000001 \le t_i \le 100000, 각 검토에 걸리는 예상 시간
  • mi=−1m_i = -1인 직원은 정확히 한 명이고, 관리자 관계는 그 직원을 뿌리로 하는 트리를 이룬다.

예제6

  1. 예제 1

    입력
    5
4 4 80
1 1 40
-1 10 60
3 5 50
4 8 70
    예상 출력
    40
0
240
120
0

  2. 예제 2

    입력
    1
-1 1 1
    예상 출력
    0

  3. 예제 3

    입력
    4
-1 5 10
1 5 20
2 5 30
3 5 40
    예상 출력
    0
0
0
0

  4. 예제 4

    입력
    4
-1 10 1
1 7 2
2 4 3
3 1 4
    예상 출력
    9
7
4
0

  5. 예제 5

    입력
    4
-1 1 100
1 2 200
2 3 300
3 4 400
    예상 출력
    0
0
0
0

  6. 예제 6

    입력
    7
-1 100000 100000
1 50000 1
1 99999 2
1 100000 3
1 1 4
1 100000 5
1 7 6
    예상 출력
    13
0
0
0
0
0
0