【题解】省选联考 2021 图函数

注意到如果 \(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)\)

【题解】省选联考 2021 图函数

上一篇:分布式环境下唯一id生成方案


下一篇:时间序列树模型特征工程汇总