hitoare日記

たまに書きます

F - Intervals on Tree(AtCoder Beginner Contest 173)

問題リンク

atcoder.jp


問題概要

\(N\)頂点の木が与えられる。各頂点には\(1,...,N\)の番号が振られている。

\(1 \leq L \leq R \leq N\)に対し

\(f(L, R)\) を、「番号\(L\)以上\(R\)以下の頂点と、両端の番号が\(L\)以上\(R\)以下の頂点であるような辺からなる部分グラフの連結成分の個数」と定義する。

\(\sum_{L=1}^N \sum_{R=1}^N f(L,R)\)を求めよ。

解法

 各\(L,R\)に対し、できる部分グラフは森(各連結成分が木であるグラフ)となる。

このグラフには次のような性質がある:

  • (連結成分の個数) = (頂点の個数) - (辺の本数)

これは各連結成分に対し(頂点の個数)-(辺の本数)=1であることからわかる。

よって、求める値は

\(L\)と\(R\)を動かした時の

(頂点の個数の合計) - (辺の本数の合計)

となる。

頂点の個数の合計は、\(i=1,...,N\)に対し

\(L \leq i \leq R\)となる\((L,R)\)の組の個数の和なので

\(\sum_{i=1}^N i \times (N-i+1)\)である。

辺の本数の合計は、辺\( (u,v)\) (ただし\( u < v\) )に対しそれを含む\((L,R)\)は

\(L \leq u\), \(v \leq R\)を満たすことが必要十分なので

\(\sum_{i=1}^{N-1} u_i \times (N-v_i+1)\)となる。

提出

https://atcoder.jp/contests/abc173/submissions/14996570

感想

 気づきさえすれば楽。

連結成分の個数は頂点・辺の個数で言い換えられるといい感じ。