34718번 - 불 뿌리기

문제

시루가 운영하는 방 탈출 카페는 $N$개의 방이 $N-1$개의 통로로 연결되어 있는 트리 형태이다. 각 방은 1ドル$부터 $N$까지의 번호가 붙어 있으며, 서로 다른 두 방은 통로를 통해 이동할 수 있다. 이때 두 방 $u,ドル $v$의 거리는 $u$에서 $v$로 가기 위해 통과해야 하는 통로의 최소 개수로 정의한다.

시루는 고객들이 진정한 탈출을 체험하도록 하기 위해 총 $M$번 불을 지르려고 한다. 한 번의 불 뿌리기 작업은 5개의 정수 $(t, u, v, r_u, r_v)$로 정의할 수 있다. 이는 시각 $t$에, $u$번 방과 거리가 $r_u$ 이하이면서 $v$번 방과 거리가 $r_v$ 이하인 모든 방에 불을 지른다는 의미다. 또한, 어떤 방에 불이 붙었다면 $K$ 시간 후에 인접한 방으로 불이 옮겨 붙는다.

$M$번의 불 뿌리기 작업 계획이 주어지면, 각 방마다 처음으로 불이 붙는 시각을 구하는 프로그램을 작성하라.

입력

첫째 줄에 방의 개수 $N$과 불 뿌리기 작업 횟수 $M,ドル 불이 전파되는데 걸리는 시간을 나타내는 정수 $K$가 공백으로 구분되어 주어진다.

그다음 줄부터 $N-1$개의 줄에 걸쳐, 통로가 연결하는 두 방의 번호 $U_i, V_i$가 공백으로 구분되어 주어진다.

그다음 줄부터 $M$개의 줄에 걸쳐, 불 뿌리기 작업을 나타내는 다섯 개의 정수 $t, u, v, r_u, r_v$가 공백으로 구분되어 주어진다.

출력

$N$개의 줄에 걸쳐 답을 출력한다.

만약 $i$번째 방에 불이 붙는다면, $i$번째 줄에 그 최초의 시각을 출력한다. 그렇지 않다면 $-1$을 출력한다.

제한

• 2ドル \le N \le 100,000円$
• 1ドル \le M \le 200,000円$
• 1ドル \le K \le 50$
• 1ドル \le U_i, V_i \le N$ ($U_i \ne V_i$)
• 1ドル \le t \le 5,000円,000円$
• 1ドル \le u,v \le N$
• 0ドル \le r_u,r_v \le N$
• 방과 통로는 트리 구조를 이룬다.

노트