ABC133 E Virus Tree 2

所感

Cはカス

問題概要

木と数Kが与えられる。イカの条件で色を塗り分けるとき、塗り分け方の個数を求めよ。

二つの異なる頂点 x,y 間の距離が2以下ならば、頂点xの色と頂点yの色は異なる。

取った方針

あるノードに注目した時、距離が2以下である、とは、以下のノードの色が違えばよい。
- 親
- 親の親
- 兄弟(同じ親の子)
深さが2以下のノードにおいて、親と親の親はそれぞれ1つずつ存在するので(理由: 木なので)、親が同じノードにK-2, K-3...と順番に数を振っていくとそれはそのノードに塗れる色の個数になる。深さが1の時はK-1, K-2...と振ることに注意する。(親の親がいないので)
最後にそれらをすべて掛ければOK

正しい方針(解説の方針)

私はBFS で解説はDFS だけど使っている事実は同じ

得られた知見

・木において距離が2 -> 親の親 or 同じ親の子
・Cはカス

解くのに必要な要素

・BFS/DFS
・Cをバグらせないこと

周辺調査によって得られた知見

特になし