题目描述

$N$ 頂点の木があります。 頂点は $1$ から $N$ まで番号が振られています。 各 $1\ <\ =\ i\ <\ =\ N\ -\ 1$ について、$i$ 番目の辺は頂点 $a_i$ と $b_i$ を繋いでいます。 辺の長さはすべて $1$ です。

いくつかの頂点はすぬけ君のお気に入りです。 お気に入りの頂点の情報は、長さ $N$ の文字列 $s$ として与えられます。 各 $1\ <\ =\ i\ <\ =\ N$ について、頂点 $i$ がお気に入りならば $s_i$ は 1 で、頂点 $i$ がお気に入りでないならば $s_i$ は 0 です。

最初、頂点はすべて白色です。 すぬけ君は次の操作をちょうど $1$ 回だけ行います。

• お気に入りの頂点 $v$ をひとつ選び、非負整数 $d$ をひとつ選ぶ。 頂点 $v$ から距離 $d$ 以内の頂点をすべて黒く塗る。

最終的な頂点の色の組合せとして考えられるものは何通りか求めてください。

输入格式

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

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

输出格式

最終的な頂点の色の組合せとして考えられるものは何通りか出力せよ。

题目大意

Snuke 君有一棵 $n$ 个节点的全白的树，其中有一些节点他喜欢，有一些节点他不喜欢。他会选择一个他喜欢的节点 $x$，然后选择一个距离 $d$，然后将所有与 $x$ 距离不超过 $d$ 的节点都染成黑色，问最后有多少种可能的染色后状态。

两个状态不同当且仅当存在一个节点，它在两个状态中不同色。

4
1 2
1 3
1 4
1100

4

5
1 2
1 3
1 4
4 5
11111

11

6
1 2
1 3
1 4
2 5
2 6
100011

8

提示

制約

• $2\ <\ =\ N\ <\ =\ 2×10^5$
• $1\ <\ =\ a_i,\ b_i\ <\ =\ N$
• グラフは木である。
• $|s|\ =\ N$
• $s$ は 0 と 1 のみからなる。
• $s$ には 1 が含まれる。

部分点

• $1300$ 点分のデータセットでは、$s$ は 1 のみからなる。

Sample Explanation 1

次の $4$ 通りです。 

Sample Explanation 2

このケースは部分点の制約を満たします。