問題
$n$ 頂点の木が与えられる。$f(i,j)$ を $i \leq j$ なる頂点からなる部分グラフの連結成分の個数とし、$\sum _ {i \leq j} f(i,j)$ を求めよ。
解説
木の部分グラフは森であり、森の連結成分の個数は「点の数 $-$ 辺の数」で求められる。 $i \leq j$ なる頂点でできるすべての森について点の数の和は $\sum _ {i = 1} ^ {n} i(n+1-i)$ で求められ、辺の数の和は $E$ をもとの木の辺集合として $\sum _ {(i,j)\in E} i(n+1-j)$ で求められるので、 $$ \sum _ {i \leq j} f(i,j) = \sum _ {i = 1} ^ {n} i(n+1-i) - \sum _ {(i,j)\in E} i(n+1-j) $$
実装
n = int(input()) ans = sum([(i + 1) * (n - i) for i in range(n)]) for i in range(n - 1): x, y = map(int, input().split()) if x > y: x, y = y, x ans -= x * (n + 1 - y) print(ans)
