問題はこちら
問題概要
頂点の木が与えられる. に対してが以下のように定義される時, を求めよ.
以上以下の頂点からなる誘導部分グラフの連結成分数
思考の流れ
式通り素直にしようとしても間に合わない.
となるの数が高速に求められればいいが無理そう.
左端を固定していろいろ考えて見るが, 頂点の追加とか削除とかが面倒で高速には求められない.
ここまでグラフが木であるという性質を用いてないので何かありそうだと思う.
木の部分グラフは森となる. さらに, 森の連結成分の個数は「頂点の個数ー辺の個数」で求められるので,
は高校数学,
はそのまま求めると時間がかかるので各辺が何回足されるかを考える.
辺が足される回数は
提出プログラム
感想
木の性質に気づけなかった.