Note

The TL for this problem is set strictly. Using a fast language is recommended.

Problem Statement

You are given a tree with $N$ vertices, numbered $1$ to $N$. For $i=1,2,\dots,N-1$, the $i$-th edge connects vertices $u_i$ and $v_i$.

Each vertex of the tree has either a lime tree or a karin tree growing on it. You are given a string $S$: if the $i$-th character of $S$ is 1, a lime tree grows on vertex $i$, and if the $i$-th character of $S$ is 0, a karin tree grows on vertex $i$.

Find the number of pairs of vertices $(l, r)$ satisfying $1 \le l \le r \le N$ such that, among the vertices on the simple path from $l$ to $r$ (including both endpoints), the number of lime trees growing on them is greater than the number of karin trees.

Input

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

Input

• $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$ are all integers $(1 \le i \le N-1)$
• $|S| = N$
• $S$ consists of the characters 0 or 1.

Output

Print the answer in $1$ line.

Sample

Sample 1

Input

5
1 2
1 3
3 4
3 5
11001

Output

7

$(l, r) = (1, 1), (1, 2), (1, 5), (2, 2), (2, 3), (2, 5), (5, 5)$ satisfy the condition.

1
1

1

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

16