かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC173 F - Intervals on Tree

問題はこちら

問題概要

{N}頂点の木が与えられる. {1\le L\le R\le N}に対して{f(L,R)}が以下のように定義される時, {\sum_{L=1}^{N}\sum_{R=L}^{N}f(L,R)}を求めよ.

{f(L,R) : }{L}以上{R}以下の頂点からなる誘導部分グラフの連結成分数

思考の流れ

式通り素直にしようとしても間に合わない.

{f(L,R)=k}となる{(L,R)}の数が高速に求められればいいが無理そう.

{\downarrow}

左端を固定していろいろ考えて見るが, 頂点の追加とか削除とかが面倒で高速には求められない.

{\downarrow}

ここまでグラフが木であるという性質を用いてないので何かありそうだと思う.

木の部分グラフは森となる. さらに, 森の連結成分の個数は「頂点の個数ー辺の個数」で求められるので,

{\sum_{L=1}^{N}\sum_{R=L}^{N}f(L,R)}

{=\sum_{L=1}^{N}\sum_{R=L}^{N}(\mbox{頂点の個数ー辺の個数})}

{=\sum_{L=1}^{N}\sum_{R=L}^{N}( (R-L+1) -(両端の頂点がL以上R以下である辺の数))}

{=\sum_{L=1}^{N}\sum_{R=L}^{N}(R-L+1)-\sum_{L=1}^{N}\sum_{R=L}^{N}(両端の頂点がL以上R以下である辺の数)}

{\sum_{L=1}^{N}\sum_{R=L}^{N}(R-L+1)}は高校数学, {\displaystyle \frac{N(N+1)(N+2)}{6}}

{\sum_{L=1}^{N}\sum_{R=L}^{N}(両端の頂点がL以上R以下である辺の数)}はそのまま求めると時間がかかるので各辺が何回足されるかを考える.

{(u,v) (u\lt v)}が足される回数は{u×(N-v+1)}

提出プログラム

感想

木の性質に気づけなかった.