No.439 チワワのなる木

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 40
作問者 : 🍡yurahuna🍡yurahuna / テスター : mayoko_mayoko_

2 ProblemId : 1094 / 出題時の順位表

問題文

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' が書かれている
さて、今年も収穫の時期がやってきました。
果たしてCさんは木から何匹のチワワを収穫することができるでしょうか?
ただし答えは32ビット型整数に収まらないことがあるので、注意してください。

入力

$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ビット型整数に収まらないことがあるので、注意してください。
最後に改行してください。

サンプル

サンプル1
入力
4
cwww
1 2
2 3
2 4
出力
2

条件を満たす組は (1, 2, 3), (1, 2, 4) です。よって収穫できるチワワは2匹です。

サンプル2
入力
5
cwwwc
1 2
2 3
3 4
4 5
出力
6

条件を満たす組は (1, 2, 3), (1, 2, 4), (1, 3, 4), (5, 4, 2), (5, 4, 3), (5, 3, 2) です。

サンプル3
入力
3
wcw
1 2
3 2
出力
0

条件を満たす組がないので、チワワを1匹も収穫することができません。

提出ページヘ