\(f(i,j) \geq k\) を満たす \((i,j)\) の組の個数を \(c_k\) とすると、\(f(i,j) = k\) を満たす \((i,j)\) の組の個数は \(c_k-c_{k+1}\) と表せます。したがって、求める答えは

\[ \begin{aligned} &\phantom{=}\sum_{k\geq 1} k(c_k-c_{k+1})\\ &=\sum_{k\geq 1} kc_k-\sum_{k\geq 1} (k-1)c_k\\ &=\sum_{k\geq 1} c_k \end{aligned} \]

より、 \(c\) の総和となります。以降は \(c_1,c_2,\ldots,c_N\) の値を順に求めることを考えます。

まず、\(f(i,j) \geq k\) が成り立つためには頂点 \(i\) から頂点 \(j\) までのパスに頂点 \(0,1,\ldots,k-1\) が全て含まれる必要があります（そしてこれらの条件は同値です）。頂点 \(0,1,\ldots,k-1\) を全て含むパスが存在する場合、ある \(2\) つの頂点 \(x_k,y_k\) が存在して以下の \(2\) つの条件は同値になります。

• パスが頂点 \(0,1,\ldots,k-1\) を全て含む。
• パスが頂点 \(x_k\) から頂点 \(y_k\) までのパスを含む。

この \(x_k,y_k\) を \(k\) の昇順に求めていくことを考えます。

まず、\(k=0\) の場合明らかに \(x_0=y_0=0\) です。

また、 \(x_{k-1},y_{k-1}\) から \(x_k,y_k\) は以下のように求めることができます：

• 頂点 \(x_{k-1},k\) のパスに頂点 \(y_{k-1}\) が含まれる場合、 \((x_k,y_k)=(x_{k-1},k)\)
• 頂点 \(k,y_{k-1}\) のパスに頂点 \(x_{k-1}\) が含まれる場合、 \((x_k,y_k)=(k,y_{k-1})\)
• 上 \(2\) つのどちらにも該当しない場合、条件を満たす \(x_k,y_k\) は存在しない。つまり、頂点 \(0,1,\ldots,k-1\) を全て含むパスが存在しない。

あるパスにある頂点が含まれるかの判定は LCA などを用いることで \(O(\log N)\) 時間で判定できます。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N \log N)\) です。