바이러스

KOI 도시는 지난 코로나19 대유행으로 큰 피해를 입었다. 그래서 앞으로 생길 수 있는 팬데믹에 철저히 대비하려 한다. 이를 위해 KOI 도시는 현재 도시 구조가 바이러스에 얼마나 취약한지 분석하려고 한다.

KOI 도시는 $N$개의 지점과 $N - 1$개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 지점을 도로만 사용해 오갈 수 있다. 즉 도시의 도로망은 트리 구조이다. 각 지점은 $0$ 이상 $N - 1$ 이하의 서로 다른 정수로 구분된다. 도로망이 트리이므로, 두 지점 $u$, $v$를 잇는 단순 경로는 하나뿐이다. 이 경로의 간선 개수를 $u$와 $v$의 거리라고 정의한다.

KOI 도시에는 $M$명이 살고 있다. 모든 $0 ≤ j ≤ M - 1$에 대해 $j$번 사람은 $P[j]$번 지점에 살며, 그 지점에서 거리가 $D[j]$ 이하인 지점을 오갈 수 있다.

바이러스학자들은 두 사람 사이의 바이러스 전파를 다음과 같이 모델링했다. 모든 $0 ≤ v ≤ N - 1$에 대해 $v$번 지점의 전파 시간은 양의 정수 $C[v]$이다. $j$번 사람이 시각 $t$에 처음 감염되었고, 이 사람에게서 바이러스를 전파받을 사람을 $k$번 사람이라 하자. 지점 $w$와 $P[j]$의 거리가 $D[j]$ 이하이고, $w$와 $P[k]$의 거리가 $D[k]$ 이하이면, $w$는 전파의 매개체가 된다.

전파의 매개체가 되는 지점이 없다면, $k$번 사람은 $j$번 사람에게서 직접 감염되지 않는다. (물론 다른 사람을 거쳐 간접적으로 감염될 수는 있다.) 매개체가 있다면, 그중 전파 시간을 최소화하는 지점의 번호를 $x$라 한다. $k$번 사람이 시각 $t + C[x]$에 아직 감염되지 않았다면, 그 시각에 $j$번 사람에 의해 감염된다. 바이러스는 서로 다른 모든 사람 쌍 $0 ≤ j, k ≤ M - 1$, $j ≠ k$에 대해 이 방식으로 퍼진다.

이 모델에서 연구진은 $0$번 사람이 시각 $0$에 감염되었을 때 다른 사람들이 언제 감염되는지 계산하려 한다. 모든 $0 ≤ j ≤ M - 1$에 대해 $j$번 사람이 처음 감염되는 시각을 구하라. 감염되지 않는 사람이라면 $-1$을 기록한다.

• $1 ≤ N ≤ 100000$
• $1 ≤ M ≤ 100000$
• 모든 $0 ≤ i ≤ N - 2$에 대해 $0 ≤ A[i], B[i] ≤ N - 1$이고 $A[i] ≠ B[i]$이다.
• 모든 $0 ≤ j ≤ M - 1$에 대해 $0 ≤ P[j], D[j] ≤ N - 1$이다.
• 모든 $0 ≤ v ≤ N - 1$에 대해 $1 ≤ C[v] ≤ 10^9$이다.