問題文

Cさんの家の庭にはチワワのなる木があります。
木は $N$ 個の頂点と $N - 1$ 本の辺からなる連結な無向グラフで表されます。頂点には $1, 2, ..., N$ と番号がつけられているものとします。
各頂点には 'c' または 'w' の文字が書かれており、以下の条件を満たす $(i, j, k)$ の組1つにつき、1匹のチワワを収穫することができます。

• $i, j, k$ は 互いに異なる $1$ 以上 $N$ 以下の整数
• 頂点 $i, j, k$ はこの順でパスをなす(すなわち、頂点 $i$ から$j$ , $j$ から $k$ の順で最短路をたどったとき、同じ辺を2度以上通ることがない)
• 頂点 $i$ には 文字 'c' が, 頂点 $j, k$ には 文字 'w' が書かれている

入力

$N$
$S$
$a_1$ $b_1$
$a_2$ $b_2$
.
.
.
$a_{N-1}$ $b_{N-1}$

• 1行目には、木の頂点の数 $N$ $(3 \leq N \leq 100000)$ が整数で与えられる。
• 2行目には、長さ $N$ の文字列 $S$ が与えられる。
• $S$ の $i$ 文字目 $s_i$ は、頂点 $i$ に書かれている文字が $s_i$ であることを示す。
• $S$ には 'c', 'w' 以外の文字は含まれない。
• 3行目から $N + 1$ 行目には、辺の情報 $a_i, b_i$ ($1 \leq i \leq N - 1,$ $a_i, b_i$ は $1$ 以上 $N$ 以下の整数) がスペース区切りの整数で与えられる。
• $a_i, b_i$ は、頂点 $a_i$ と 頂点 $b_i$ を結ぶ辺が存在することを表す。
• 同じ頂点どうしを結ぶ辺はない。すなわち、すべての $i$ について、 $a_i \neq b_i$ である。
• 同じ辺が複数与えられることはない。すなわち、すべての $i, j$ $(1 \leq i < j \leq N - 1)$ について、「$a_i \neq a_j$ または $b_i \neq b_j$」かつ「$a_i \neq b_j$ または $b_i \neq a_j$」である。
• どの頂点からどの頂点へも、いくつかの辺を経由して到達可能である。

出力

木から収穫できるチワワの匹数を1行で出力してください。
ただし答えは32ビット型整数に収まらないことがあるので、注意してください。
最後に改行してください。

サンプル

4
cwww
1 2
2 3
2 4

2

5
cwwwc
1 2
2 3
3 4
4 5

6

3
wcw
1 2
3 2

0