解答:Submission #15077700 - AtCoder Beginner Contest 173
解法:超重要な公式として「森の連結成分 = 頂点数 - 辺数」がある。これはn個の頂点から1つずつ辺を増やすことで連結成分数が1つずつ減っていくことに対応する。また、森は閉路がないため、追加した辺は必ず連結成分減少に寄与することが分かる。
よって、頂点数と辺数を別々に数えればよい。
頂点数はグラフの構造によらず[L, R]の中に何個整数点があるかという問題で、これは「「1からnまでの累積和」の累積和」が答えである。
辺数はそれぞれの辺ごとに何回数えられるかを考える。辺(u, v)はL≦uかつv≦RであるL, Rを選んだ時に数えられるため、u * (n - v + 1)回数えられる。これを足し上げればよい。