求めるべき値を、全ての \(u = 1, 2, \dots, N\) に対する以下の値の総和と言い換えます。

• 頂点 \(1\) から頂点 \(u\) まで、番号が \(l\) 以上 \(r\) 以下の辺のみを辿って到達できるような \((l, r)\) の組の総数。

どのような　\((l, r)\) に対しても頂点 \(1\) に到達することができるので、\(u = 1\) のときの値は \(\frac{N(N-1)}{2}\) です。\(u \neq 1\) のとき、頂点 \(1\) から頂点 \(u\) への最短経路に含まれる辺の番号の最小値と最大値をそれぞれ \(m, M\) とおくと、\((l, r)\) の満たすべき条件は \(1 \leq l \leq m\) かつ \(m \leq r \leq N-1\) であり、\((l, r)\) の組は \(m \times (N - M)\) 通りあります。

頂点 \(1\) を始点として、通った辺の番号の最小値および最大値を記録しながら DFS ないし BFS を行うことで、全ての \(u\) に対する値を効率的に求めることができます。よって、この問題を \(O(N)\) で解くことができました。