解法
\(0\)-indexed, 半開区間で考える． 森の誘導部分グラフは森になる． よって， グラフ \(G\) が森のとき，
(\(G\)の connected component の個数) = \(|V(G)| - |E(G)|\)
となる．
頂点集合が区間 \([l,r)\) となる \(G\) の誘導部分グラフの 頂点集合と辺集合をそれぞれ \(|V_{l,r}|\), \(|E_{l,r}|\) と書く． $$ ans = \sum_{0 \leq l < r \leq N} (|V_{l,r}| - |E_{l,r}|) $$ となる．
前半の項を求める． \(|V_{l,r}| = r-l\) が等しい項をまとめる．
長さが \(1\) の区間は \(N\) 個， 長さが \(2\) の区間は \(N-1\) 個， \(\vdots\) 長さが \(N\) の区間は \(1\) 個 となる．
後半の項を求める． 和をとる順序を変えて， edge \(\,(a,b)\, \in E(G)\) に対して， 組 \((l,r)\) のうち \(E_{l,r}\) の条件を満たすものの個数 を数える． \(a < b\) を仮定すると，\(E_{l,r}\) において満たすべき条件は，
\(l \leq a\) かつ \(b < N\)
となる．このような \(l,r\) の組は \((a+1)(N-b)\) 個．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
rep(i,n-1){
ll a,b; cin >> a >> b;
a--,b--;
if(a > b) swap(a,b);
ed[i] = {a,b};
}
ll ans = 0;
rep1(i,n) ans += i*(n-i+1);
for(auto [a,b]: ed){
ans -= (a+1)*(n-b);
}
return 0;
}
