木において「連結成分の数 = 頂点数 - 辺の数」で求められることに注目する。 直感的に、頂点が増えると連結成分の数が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$が答えとなる。
