ABC173 F. Intervals on Tree
問題
N頂点N-1辺からなる木が与えられる。
頂点には1からNまで番号がつけられている。
整数1 <= L <= R <= Nについて、関数f(L,R)を以下のように定める。
- Sを番号がL以上R以下の頂点からなる集合とする
- 頂点集合Sと両端がSに属する辺からなる部分グラフにおける連結成分の個数をf(L, R)とする
このとき、Σ_{L=1}^N Σ_{R=L}^N f(L, R)を求めよ。
制約
- 1 <= N <= 2*10^5
解法
ある辺eに注目すると、そのeがaとbをつないでいる場合、Lがa以下、Rがb以上の場合に含まれる。
この辺eが追加されると、上記のような(L,R)で、連結成分が1つ減ることになる。
したがって、辺がない場合での連結成分数の合計を求めて、各辺について、Lがa以下、Rがb以上の場合、a*(N+1-b)個のL,Rのペアで連結成分が-1になるの引いていけば良い。
「辺がない場合での連結成分数の合計」は、Σ_{i=1}^N (N*(N+1)/2)で求められて、これから各辺のa*(N+1-b)を引いていけばよいので、O(N)で求められる。
