Problem Statement

There is a tree with $N$ vertices. The vertices are numbered $1$ through $N$. For each $1 ≤ i ≤ N - 1$, the $i$-th edge connects vertices $a_i$ and $b_i$. The lengths of all the edges are $1$.

Snuke likes some of the vertices. The information on his favorite vertices are given to you as a string $s$ of length $N$. For each $1 ≤ i ≤ N$, $s_i$ is 1 if Snuke likes vertex $i$, and 0 if he does not like vertex $i$.

Initially, all the vertices are white. Snuke will perform the following operation exactly once:

• Select a vertex $v$ that he likes, and a non-negative integer $d$. Then, paint all the vertices black whose distances from $v$ are at most $d$.

Find the number of the possible combinations of colors of the vertices after the operation.

Constraints

• $2 ≤ N ≤ 2×10^5$
• $1 ≤ a_i, b_i ≤ N$
• The given graph is a tree.
• $|s| = N$
• $s$ consists of 0 and 1.
• $s$ contains at least one occurrence of 1.

Partial Score

• In the test set worth $1300$ points, $s$ consists only of 1.

Input

The input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}
s

Output

Print the number of the possible combinations of colors of the vertices after the operation.