注意

この問題の TL は厳しめに設定されています。 高速な言語の使用を推奨します。

問題文

頂点に$1$ から $N$ の番号が付けられた $N$ 頂点の木が与えられます。 $i=1,2,\dots,N-1$ について $i$ 番目の辺は頂点 $u_i$ と $v_i$ を結びます。

木の各頂点には、ライムの木かカリンの木のいずれかが生えています。 文字列 $S$ が与えられ、 $S$ の $i$ 番目の文字が 1 のとき頂点 $i$ にはライムの木が、 $S$ の $i$ 番目の文字が 0 のとき頂点 $i$ にはカリンの木が生えています。

$1 \le l \le r \le N$ を満たす頂点の組 $(l, r)$ であって、 $l$ から $r$ への両端を含む単純パス上の頂点に生えているライムの木の本数が カリンの木の本数よりも多いものの個数を答えてください。

入力

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$S$

入力

• $1 \le N \le 100000$
• $1 \le u_i < v_i \le N \quad (1 \le i \le N-1)$
• $N, u_i, v_i$ は全て整数 $(1 \le i \le N-1)$
• $|S| = N$
• $S$ は 0 または 1 の文字からなる。

出力

答えを $1$ 行で出力せよ。

サンプル

サンプル1

入力サンプルをコピー

入力

5
1 2
1 3
3 4
3 5
11001

出力

7

$(l, r) = (1, 1), (1, 2), (1, 5), (2, 2), (2, 3), (2, 5), (5, 5)$ が条件を満たします。

1
1

1

10
2 8
4 9
1 6
3 7
1 8
5 8
1 10
1 7
7 9
0111110100

16