注意到如果 \(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)\) 。
原文：https://www.cnblogs.com/qiulyqwq/p/15229173.html