Örnattack

문제

Ekorrarna och örnarna har krigat sedan urminnes tider. Gammelekorren är en mästare på astrologi och har förutspått att örnarna snart kommer försöka sig på en sista attack mot storträdet. Enligt gammelekorren kommer ett antal örnar flyga in i trädet i hög fart för att få hela trädet att skaka så att ekorrarna riskerar att ramla ned.

Trädet består av $N-1N\; -\; 1$ grenar, som går samman i $NN$ olika punkter som vi kallar för noder (varav trädets stam är nod $11$). Varje gren i trädet går alltså mellan två av dessa noder. Gammelekorren har förutspått i vilken av trädets $NN$ noder var och en av örnarna kommer krascha och med vilken fart. Han vill veta hur mycket varje nod kommer skaka under attacken för att kunna varna alla ekorrar om de farligaste noderna. Tyvärr är gammelekorren inte lika bra på programmering som på astrologi, så han har anställt dig för att räkna ut hur mycket varje nod kommer skaka under attacken.

När en örn kraschar med fart $vv$ i nod $uu$ börjar nod $uu$ skaka med styrkan $vv$. Skakningen sprider sig sedan genom de grenar som utgår från nod $uu$. När skakningen når en viss nod kommer den spridas genom alla grenar som möts i den nya node, förutom den som skakningen kom från. Skakstyrkan sprids i lika delar längs dessa nya grenar, så om skakningen hade styrka $vv$ och sprids längs $kk$ grenar kommer skakningen som färdas längs grenarna ha styrkan $\frac{v}{k}\backslash frac\{v\}\{k\}$. Detta pågår ända tills skakningen till slut når noder som inte har några andra grenar än den från vilken skaningen kom från, där skakningen slutas spridas vidare.

Du kan anta att skakningen från en krasch hinner sprida sig genom hela trädet och försvinna innan nästa örn kraschar. För var och en av noderna i trädet vill gammelekorren veta summan av alla skakningars styrkor som noden kommer utsättas för.

입력

På den första raden finns heltalet $NN$ ($1\le N\le 1000001\; \backslash le\; N\; \backslash le\; 100\backslash ,000$), antalet noder i trädet. De följande $N-1N-1$ raderna innehåller två heltal $aa$ och $bb$ ($1\le a,b\le N1\; \backslash le\; a,b\; \backslash le\; N$), vilket betyder att det går en gren mellan nod $aa$ och nod $bb$.

Därefter följer en rad med heltalet $KK$ ($1\le K\le 1000001\; \backslash le\; K\; \backslash le\; 100\backslash ,000$), antalet örnar som kommer attackera. Slutligen följer $KK$ rader som beskriver örnarna i den ordning de kraschar in i trädet. På varje rad finns två heltal, noden $uu$ ($1\le u\le N1\; \backslash le\; u\; \backslash le\; N$) där örnen kommer krascha och örnens fart $vv$ ($1\le v\le {10}^{9}1\; \backslash le\; v\; \backslash le\; 10^9$).

출력

Skriv ut en rad för varje nod i ordningen $11$, $22$, $\dots \backslash dots$ med summan av alla skakningars styrkor noden kommer utsättas för. Ditt svar anses korrekt om det har ett absolut eller relativt fel om högst ${10}^{-5}10^\{-5\}$.

힌트

[이미지 1]

Figure 1: Första örnen.

[이미지 2]

Figure 2: Andra örnen.

Den första örnen kraschar i nod $44$ med fart $55$. Från nod $44$ sprids skakningen endast till nod $33$ och från nod $33$ till både nod $11$ och $55$. Från nod $55$ har skakningen ingenstans att ta vägen men från nod $11$ sprids den till nod $22$.

Den andra örnen kraschar i nod $33$ med fart $66$. Från nod $33$ sprids skakningen till nod $11$, $44$ och $55$. Skakningarna i nod $44$ och $55$ har ingenstans att ta vägen men skakningen i nod $11$ sprids till nod $22$.

För att få svaren ska varje nods skakningar adderas, exempelvis blir svaret $2.5+2=4.52.5+2=4.5$ i nod $11$ och $5+6=115+6=11$ i nod $33$.