No.439

木を根付き木と考える. 頂点 $i$ の子の集合を $C_i$ とする.

ある頂点 $i$ について, $d_c(i)$ を頂点 $i$ を含む頂点 $i$ の子孫にある c の数とする. $d_w$ も同様に定義する.

$d_c, d_w$ は葉から DP で求めることができる.

このとき, 木にある cww の数であるが, 真ん中の w が頂点 $i$ にあるとし, 頂点 $i$ の子のひとつを $j$ とすると,

• 頂点 $j$ を含む頂点 $j$ の子孫の中に c があり, 木から頂点 $i$ と頂点 $j$ を含む頂点 $j$ の子孫を取り除いた中に w がある
• 頂点 $j$ を含む頂点 $j$ の子孫の中に w があり, 木から頂点 $i$ を含む頂点 $i$ の子孫を取り除いた中に c がある

のどちらかとなる. それぞれのパターン数は,

$$\sum_{j \in C_i} d_c(j) \cdot (d_w(0) - d_w(j) - 1) \\ \sum_{j \in C_i} d_w(j) \cdot (d_c(0) - d_c(i))$$

となる.