問題文

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