독수리 공격

다람쥐와 독수리는 아주 오래전부터 전쟁을 벌여 왔다. 늙은 다람쥐는 점성술의 대가로, 독수리들이 곧 큰 나무를 향해 마지막 공격을 시도하리라는 것을 예언했다. 늙은 다람쥐에 따르면 여러 마리의 독수리가 빠른 속도로 나무에 돌진해 나무 전체를 흔들어, 다람쥐들이 떨어질 위험에 처하게 된다고 한다.

나무는 $N-1$개의 가지로 이루어져 있고, 이 가지들은 $N$개의 지점에서 만난다. 이 지점을 노드라고 부른다(나무의 줄기는 노드 $1$이다). 따라서 나무의 각 가지는 이 노드들 중 두 개를 연결한다. 늙은 다람쥐는 나무의 $N$개 노드 중 어느 노드에 각 독수리가 충돌할지와 그 속도를 예언했다. 그는 공격 중에 각 노드가 얼마나 흔들릴지 알아내어, 모든 다람쥐에게 가장 위험한 노드를 경고하려 한다. 안타깝게도 늙은 다람쥐는 점성술만큼 프로그래밍을 잘하지 못해서, 공격 중에 각 노드가 얼마나 흔들릴지 계산할 사람으로 당신을 고용했다.

독수리가 속도 $v$로 노드 $u$에 충돌하면 노드 $u$는 세기 $v$로 흔들리기 시작한다. 그런 다음 흔들림은 노드 $u$에서 뻗어 나가는 가지를 따라 퍼진다. 흔들림이 어떤 노드에 도달하면, 그 노드에 모이는 모든 가지 중 흔들림이 온 가지를 제외한 나머지 가지로 퍼진다. 흔들림의 세기는 이 새로운 가지들에 똑같이 나뉘어 전달되므로, 세기 $v$의 흔들림이 $k$개의 가지로 퍼지면 각 가지를 따라 이동하는 흔들림의 세기는 $\frac{v}{k}$이다. 이 과정은 흔들림이 마침내, 흔들림이 온 가지 외에 다른 가지가 없는 노드에 도달할 때까지 이어지며, 그곳에서 흔들림은 더 이상 퍼지지 않는다.

한 번의 충돌로 생긴 흔들림은 다음 독수리가 충돌하기 전에 나무 전체를 퍼져 나가 사라진다고 가정할 수 있다. 나무의 각 노드마다 늙은 다람쥐는 그 노드가 받게 될 모든 흔들림 세기의 합을 알고 싶어 한다.

첫째 줄에 나무의 노드 수를 나타내는 정수 $N$이 주어진다($1 \le N \le 100\,000$). 다음 $N-1$개 줄에는 두 정수 $a$와 $b$가 주어지며($1 \le a,b \le N$), 이는 노드 $a$와 노드 $b$ 사이에 가지가 있음을 뜻한다.

그다음 줄에는 공격할 독수리의 수를 나타내는 정수 $K$가 주어진다($1 \le K \le 100\,000$). 마지막으로 독수리들이 나무에 충돌하는 순서대로 독수리를 설명하는 $K$개 줄이 주어진다. 각 줄에는 독수리가 충돌할 노드 $u$($1 \le u \le N$)와 독수리의 속도 $v$($1 \le v \le 10^9$)가 주어진다.

노드 $1$, $2$, $\dots$ 순서대로 각 노드가 받게 될 모든 흔들림 세기의 합을 한 줄에 하나씩 출력한다. 답의 절대 오차 또는 상대 오차가 $10^{-5}$ 이하이면 정답으로 인정된다.

그림 1: 첫 번째 독수리.

그림 2: 두 번째 독수리.

첫 번째 독수리는 노드 $4$에 속도 $5$로 충돌한다. 노드 $4$에서 흔들림은 노드 $3$으로만 퍼지고, 노드 $3$에서는 노드 $1$과 노드 $5$ 모두로 퍼진다. 노드 $5$에서는 흔들림이 더 갈 곳이 없지만 노드 $1$에서는 노드 $2$로 퍼진다.

두 번째 독수리는 노드 $3$에 속도 $6$으로 충돌한다. 노드 $3$에서 흔들림은 노드 $1$, $4$, $5$로 퍼진다. 노드 $4$와 노드 $5$의 흔들림은 더 갈 곳이 없지만 노드 $1$의 흔들림은 노드 $2$로 퍼진다.

답을 구하려면 각 노드의 흔들림을 모두 더해야 한다. 예를 들어 노드 $1$에서 답은 $2.5+2=4.5$이고, 노드 $3$에서 답은 $5+6=11$이다.