Eagle Attack

Squirrels and eagles have been at war since time immemorial. The old squirrel is a master of astrology and has predicted that the eagles will soon attempt one final attack on the great tree. According to the old squirrel, several eagles will fly into the tree at high speed to make the whole tree shake, so that the squirrels risk falling down.

The tree consists of $N - 1$ branches, which meet at $N$ different points that we call nodes (the trunk of the tree is node $1$). Each branch of the tree therefore runs between 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 so that he can 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 work out how much each node will shake during the attack.

When an eagle crashes at speed $v$ into node $u$, node $u$ starts shaking with strength $v$. The shaking then spreads through the branches that leave node $u$. When the shaking reaches a node, it spreads through all branches that meet at the new node, except the one the shaking came from. The shaking strength is divided equally along these new branches, so if the shaking had strength $v$ and spreads along $k$ branches, the shaking traveling along the branches has strength $\frac{v}{k}$. This continues until the shaking finally reaches nodes that have no branches other than the one the shaking came from, where the shaking stops spreading.

You may assume that the shaking from one crash has time to spread through the whole tree and die out before the next eagle crashes. For each of the nodes in the tree, the old squirrel wants to know the sum of the strengths of all shakings that the node will be subjected to.

The first line contains the integer $N$ ($1 \le N \le 100\,000$), the number of nodes in the tree. The following $N-1$ lines contain two integers $a$ and $b$ ($1 \le a,b \le N$), which means there is a branch between node $a$ and node $b$.

Then follows a line with the integer $K$ ($1 \le K \le 100\,000$), the number of eagles that will attack. Finally, $K$ lines follow that describe the eagles in the order they crash into the tree. Each line contains two integers, the node $u$ ($1 \le u \le N$) where the eagle will crash and the eagle's speed $v$ ($1 \le v \le 10^9$).

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

Figure 1: The first eagle.

Figure 2: The second eagle.

The first eagle crashes into node $4$ at speed $5$. From node $4$ the shaking spreads only to node $3$, and from node $3$ to both node $1$ and node $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$ at speed $6$. From node $3$ the shaking spreads to nodes $1$, $4$ and $5$. The shakings in nodes $4$ and $5$ have nowhere to go, but the shaking in node $1$ spreads to node $2$.

To get the answers, add up the shakings of each node. For example, the answer at node $1$ becomes $2.5+2=4.5$ and at node $3$ it becomes $5+6=11$.