問題リンク
問題概要
\(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
感想
気づきさえすれば楽。
連結成分の個数は頂点・辺の個数で言い換えられるといい感じ。