Home

Contest: Task: Related: TaskE TaskG

Score : $1900$ points

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.

Sample Input 1

Sample Output 1

The following four combinations of colors of the vertices are possible:

Sample Input 2

Sample Output 2

This case satisfies the additional constraint for the partial score.

Sample Input 3