1497 - Walkin' on Numbered Tree

問題

$N$ 個の頂点と $N - 1$ 本の辺からなる木があります。$i$ $(1 \leq i \leq N - 1)$ 番目の辺は頂点 $u_i$ と 頂点 $v_i$ をつないでいます。

$N$ 匹のゴリア君がいま頂点 $1$ におり、それぞれのゴリア君が何も書かれていない黒板を持っています。
ゴリア君 $i$ $(1 \leq i \leq N)$ は現在いる頂点に隣接する頂点へ移動することを繰り返して、頂点 $i$ まで移動します。この際、頂点 $i$ までの距離が最短となる経路上を移動します。
すべてのゴリア君は頂点 $j$ $(1 \leq j \leq N)$ に訪れたとき、以下のことを順に行います。

1. 整数 $C_j$ を黒板に書かれている整数の末尾に書き足す。ただし、黒板に何も書かれていない場合は、黒板に整数 $C_j$ を書く。
2. 黒板に書かれた整数が $T$ の倍数であるならば、幸福度 $P_j$ を得る。

なお、すべてのゴリア君が最初頂点 $1$ にいますが、これは頂点 $1$ に訪れたものとして考えます。
また、最初すべてのゴリア君の幸福度は $0$ であるとします。

最終的にゴリア君 $i$ が得る幸福度の総和を $X_i$ とします。
$\displaystyle\sum_{i = 1}^N X_i$ を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $T$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N - 1}$ $v_{N - 1}$
$C_1$ $P_1$
$C_2$ $P_2$
$\vdots$
$C_N$ $P_N$

出力

$\displaystyle\sum_{i = 1}^N X_i$ を出力せよ。出力の最後に改行を入れること。

制約

すべての入出力ケースについて以下を満たす。

• $1 \leq N \leq 10^5$
• $1 \leq T \leq 100$
• $1 \leq u_i , v_i \leq N$ $(1 \leq i \leq N - 1)$
• $1 \leq C_i \leq 9$ $(1 \leq i \leq N)$
• $1 \leq P_i \leq 10^5$ $(1 \leq i \leq N)$
• 与えられるグラフは木である
• 入力はすべて整数

入出力例

入力例１

4 4
1 2
2 3
2 4
3 1
2 2
4 3
8 4

出力例１

13

• ゴリア君 $1$
• 頂点 $1$ に訪れる。黒板に書かれた整数は $3$ となる。
• ゴリア君 $2$
• 頂点 $1$ に訪れる。黒板に書かれた整数は $3$ となる。
• 頂点 $2$ に訪れる。黒板に書かれた整数は $32$ となる。幸福度は $2$ となる。
• ゴリア君 $3$
• 頂点 $1$ に訪れる。黒板に書かれた整数は $3$ となる。
• 頂点 $2$ に訪れる。黒板に書かれた整数は $32$ となる。幸福度は $2$ となる。
• 頂点 $3$ に訪れる。黒板に書かれた整数は $324$ となる。幸福度は $2 + 3 = 5$ となる。
• ゴリア君 $4$
• 頂点 $1$ に訪れる。黒板に書かれた整数は $3$ となる。
• 頂点 $2$ に訪れる。黒板に書かれた整数は $32$ となる。幸福度は $2$ となる。
• 頂点 $4$ に訪れる。黒板に書かれた整数は $328$ となる。幸福度は $2 + 4 = 6$ となる。

よって、$0 + 2 + 5 + 6 = 13$ が答えです。

入力例2

4 6
1 2
2 3
3 4
3 3
3 5
3 7
6 8

出力例2

8

入力例3

4 9
3 1
3 2
3 4
9 1
8 1
5 2
5 1

出力例3

4

入力例4

7 2
6 1
5 2
4 3
6 4
7 5
7 6
2 6
6 3
7 5
7 5
1 8
6 1
5 8

出力例4

51