提出したコード

木において「連結成分の数 = 頂点数 - 辺の数」で求められることに注目する。 直感的に、頂点が増えると連結成分の数が1増え、辺の数が増えると連結成分の数が1減るという感じで理解できる。 $f(L, R)$もこれで求められる。

$$ \begin{aligned} &f(L, R) \\
&= 区間[L \ R]に含まれる点の数 \\
&- 両端が区間[L \ R]に含まれる辺の数 \\
\end{aligned} $$

これをLとRの全通りで求めて総和をとればよい。 頂点数と辺の数はそれぞれ独立に求めていけばよい。

$$ \begin{aligned} &\sum_{L,R} f(L,R) \\
&= \sum_{L,R} 区間[L \ R]に含まれる頂点の数 \\
&- \sum_{L,R} 両端が区間[L \ R]に含まれる辺の数 \\
&= V - E \end{aligned} $$

以下のように図示してみると、ある頂点$i$は全体で$(i+1)(N-i)$回現れるので、すべての$i$でこれの総和を取って$V$とすればよい。 同様にある辺$(u, v)$は全体で$(u+1)(N-v)$回現れるので、すべての辺について総和を取って$E$とする。 $V-E$が答えとなる。