루미 알고리즘

#1546골드Eagle Attack

PO 2022 온라인 예선코딩출제 Victor Vatn, Gustav Kalander영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

The squirrels and eagles have been at war since ancient times. The Old Squirrel is a master of astrology and has predicted that the eagles will soon attempt one last attack on the Great Tree. According to the Old Squirrel, a number of eagles will fly into the tree at high speed to make the whole tree shake, causing the squirrels to risk falling down.

The tree consists of N - 1 branches, which connects N different points that we call nodes (with the tree's trunk being node 1). Each branch in the tree thus connects two of these nodes. The Old Squirrel has predicted which of the tree's N nodes each of the eagles will crash into and at what speed. He wants to know how much each node will shake during the attack to warn all the squirrels about the most dangerous nodes. Unfortunately, the Old Squirrel is not as good at programming as he is at astrology, so he has hired you to calculate how much each node will shake during the attack.

When an eagle crashes with speed v into node u, node u begins to shake with strength v. The shaking then spreads through the branches that extend from node u. When the shaking reaches a certain node, it will spread through all the branches that meet at the new node, except the one the shaking came from. The shaking strength spreads equally along these new branches, so if the shaking had strength v and spreads along k branches, the shaking traveling along the branches will have strength v/k. This continues until the shaking eventually reaches nodes that have no other branches than the one from which the shaking came, where the shaking stops spreading.

You can assume that the shaking from a crash spreads through the entire tree and dissipates before the next eagle crashes. For each of the nodes in the tree, the Old Squirrel wants to know the sum of all the shaking strengths that the node will be subjected to.

Input

The first line contains the integer N (1 ≤ N ≤ 100,000), the number of nodes in the tree. The following N-1 lines each contain two integers a and b (1 ≤ a, b ≤ N), indicating that there is a branch between node a and node b.

Next, there is a line with the integer K (1 ≤ K ≤ 100,000), the number of eagles that will attack. Finally, there are K lines describing the eagles in the order they crash into the tree. Each line contains two integers, the node u (1 ≤ u ≤ N) where the eagle will crash and the eagle's speed v (1 ≤ v ≤ 10^9).

Output

Print one line for each node in the order 1, 2, … with the sum of all shaking strengths that the node will be subjected to. Your answer is considered correct if it has an absolute or relative error of at most 10^-5.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
115The ith edge connects node i and node i+1 (for all 1 ≤ i ≤ N-1).
2301 ≤ N,K ≤ 2000
351 ≤ N ≤ 2000
450No additional constraints.

Explanation of Sample 2

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: First eagle.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: Second eagle.

The first eagle crashes into node 4 with a speed of 5. From node 4, the shaking spreads only to node 3 and from node 3 to both nodes 1 and 5. From node 5, the shaking has nowhere to go, but from node 1 it spreads to node 2.

The second eagle crashes into node 3 with a speed of 6. From node 3, the shaking spreads to nodes 1, 4, and 5. The shaking in nodes 4 and 5 has nowhere to go, but the shaking in node 1 spreads to node 2.

To get the answers, the shaking values for each node are added together, for example, the answer is 2.5+2=4.5 in node 1 and 5+6=11 in node 3.

예제

예제 1

입력
4
1 2
2 3
3 4
3
2 7
3 4
2 3
출력
7
12
9
7

예제 2

입력
5
1 2
1 3
3 4
3 5
2
4 5
3 6
출력
4.5
4.5
11
7
4.5

출처 표기

출처: Programmeringsolympiaden 2022년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.