ABC173F

• 木はちょうど頂点数-1本の辺を持つ
• よって森に含まれる木の個数は頂点数vと辺の数eから求められる
  • $f(L,R)=v(L,R)-e(L,R)$
  • 閉路のないグラフの連結成分の個数
• 演算順序の変更
  • ${\sum }_L{\sum }_{R}f(L,R)={\sum }_L{\sum }_{R}v(L,R)-{\sum }_L{\sum }_{R}e(L,R)$
  • ${\sum }_L{\sum }_R{1}_{L\le i\le R}=(N-(i-1))((i-1)+1)$

python

def main():
    v = 0
    e = 0
    N = int(input())
    for i in range(N):
        v += (N - i) * (i + 1)

    for i in range(N - 1):
        v1, v2 = sorted(map(int, input().split()))
        v1 -= 1
        v2 -= 1
        e += (N - v2) * (v1 + 1)

    debug(": e, v", e, v)
    print(v - e)

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