24918번 - 균형 발전 서브태스크

2062 대선에 나선 경곽당 정후는 경쟁자인 무소속 동현이를 제치고 대통령에 당선되었다!

정후는 자신의 공약인 지역 균형 발전을 위해 먼저 목표 지역을 트리 형태로 구성하였다. 즉, 엄선한 N 개의 목표 지역을 정점으로 하며 두 지역을 잇는 N - 1 개의 간선을 가지는 트리를 구성하였다. 트리의 루트는 경기과학고등학교가 있는 지역 1이다.

다음으로 정후는 발전 계획, 즉 N 개의 목표 지역의 활성화 순서 계획을 나타내는 길이 N의 순열 T를 수립하였다. 현재 시각은 0이며, 시각 i가 되었을 때 지역 T_i를 활성화한다. 이 과정에서 계획에 없던 활성화가 일어날 수도 있는데, 지역의 누적 유입 인구가 C_i 이상이 될 때이다. 지역의 누적 유입 인구는 최초에 0이다.

계획에 있든 없든, 지역 i가 활성화되면 즉시 거리가 R_i 이하인 자손 지역 모두, 즉 지역 i를 조상으로 가지면서 지역 i까지의 거리가 R_i 이하인 지역 모두에 X_i만큼의 인구 이동이 일어난다. 즉, 거리가 R_i 이하인 자식 지역 모두의 누적 유입 인구가 X_i만큼 증가한다. 활성화가 연쇄적으로 일어날 수도 있으며, 연쇄 활성화의 순서가 여러 가지가 가능할 때에는 아무 순서로 활성화가 일어난다.

발전 계획을 살펴보던 정후를 위해 각 지역이 활성화되는 시각을 구하자.

첫째 줄에 하나의 정수 N이 주어진다. 둘째 줄부터 N - 1 개의 줄에 걸쳐 세 정수 u_i, v_i, w_i가 공백으로 구분되어 주어진다. 트리에서 지역 u_i와 지역 v_i가 거리 w_i의 길로 연결되어 있음을 의미한다. N + 1째 줄에 N 개의 정수 T_i가 공백으로 구분되어 주어진다. N + 2째 줄부터 N 개의 줄에 걸쳐 i째 줄에 세 정수 C_i, R_i, X_i가 공백으로 구분되어 주어진다.

유일한 줄에 각 지역이 활성화되는 시각을 나타내는 N 개의 정수를 차례로 공백으로 구분하여 출력한다.

• 1 ≤ N ≤ 200,000
• 1 ≤ T_i ≤ N
• i ≠ j이면 T_i ≠ T_j.
• 0 ≤ R_i ≤ 10¹⁵
• 1 ≤ C_i ≤ 10¹⁵
• 1 ≤ X_i, w_i ≤ 10⁹
• 1 ≤ u_i, v_i ≤ N, u_i ≠ v_i
• 중복 간선이 없다.
• 주어지는 모든 수는 정수이다.
• 목표 지역은 트리 형태이다.

• 1 ≤ N ≤ 1,000

• X_i = 1
• R_i ≤ 1
• u_i = i, v_i = i + 1, w_i = 1

• u_i = i, v_i = i + 1

• w_i = 1
• R_i = N

• R_i는 쌍끼리 서로 같다.
• w_i = 1

추가 제한 조건이 없다.