No.899 γatheree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 26
作問者 : niuezniuez / テスター : Lemma299Lemma299
9 ProblemId : 3405 / 出題時の順位表
問題文最終更新日: 2019-10-05 00:11:08

問題文

niuez くんの街にある神木には木の妖精がいます.
ある木の頂点に「三つ木もの」(tri-butree)を置くと,近くにいる妖精はその頂点に集合します.
niuez くんはこれで遊んでようと思いました.

$0$ から $N-1$ までの番号のついた $N$ 頂点,$N-1$ 辺からなる無向木があり,$i \ (0 \leq i < N-1)$ 番目の辺は頂点 $u_i$ と $v_i$ を端点とします.
また,頂点 $i \ (0 \leq i \le N - 1)$ には $A_i$ 匹の妖精がいます.
妖精は頂点にしかとどまらず,とどまっている頂点から距離が $2$ 以下の頂点に「三つ木もの」が置かれると,「三つ木もの」をおいた頂点に移動するという習性を持っています.
移動後, 妖精は移動先の頂点にとどまります
ただし,ある頂点対 $a, b$ の距離とは $a, b$ のパスに含まれる辺の数とします.
以下の $Q$ 個の ${\rm query}$ を順に処理してください.

  • $x$
    • 頂点 $x$ に「三つ木もの」を置く.その後,頂点 $x$ にいる妖精の数を求める.

入力

$N$
$u_0 \  v_0$
$\cdots$
$u_{N-2} \  v_{N-2}$
$A_0 \  A_1 \ \cdots \  A_{N-1}$
$Q$
$x_0$
$\cdots$
$x_{Q-1}$
  • $2 \leq N \leq 10^5$
  • $0 \leq u_i, v_i < N$
    • $u_i \neq v_i$
    • $(u_i, v_i) = (u_j, v_j) \Leftrightarrow i = j$
  • $0 \leq A_i \leq 10^5$
  • $1 \leq Q \leq 10^5$
  • $0 \leq x_i < N$
  • 入力はすべて整数

出力

$Q$ 行出力し,$i$ 行目には $i$ 番目の ${\rm query}$ の答えを整数で一行に出力してください.

サンプル

サンプル1
入力
10
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
0 1 2 3 4 5 6 7 8 9
3
1
4
0
出力
34
34
45

頂点$1$から距離$2$以下の頂点は, $0, \ 1, \ 2, \ 3, \ 4, \ 7, \ 8, \ 9$です.
なので, 頂点$1$には, $0+1+2+3+4+7+8+9=34$匹の妖精が集まってきます.
また, 最後のクエリの頂点$0$では, 木上にいるすべての妖精が頂点$0$に集合します.

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。