注意到如果 \(v\) 对 \(f(u,G)\) 产生贡献,那么 \(v\lequ\) 且 \(v\) 能经过 \([v,n]\) 中的点到 \(u\),\(u\) 也能经过 \([v,n]\) 中的点到 \(v\) 。令 \(g_{u,v}\) 表示 \(u\) 能经过 \([\min (u,v),n]\) 中的点到 \(v\),注意到 \(h(G)\) 为 \(\sum\limits_{u}\sum\limits_{v\leq u}[g_{u,v}\and g_{v,u}]\) 。
为了解决原问题,重新定义 \(g_{u,v}\) 为所有合法路径,最大的编号最小的边的编号是多少。接下来求 \(g_{u,v}\),用 Floyd 求即可。
时间复杂度 \(O(n^3+m)\) 。