幸せな明日を願うけど 底なしの孤独をどうしよう

もう うめき声しか出ない  わたし ぎゅうぐらりん

强度最低的一集。

考虑一个点 $(p_1,...,p_k)$ 的距离应该怎么算。

不难发现只可能是他们奇/偶最短路的最大值。也就是在距离最大的点到达前，其他所有的点都在某条边上来回横条。

记 $f_{u,0/1}$ 表示点 $u$ 的偶/奇最短路，那么答案就是

$$\sum_{S=\{p_1,...,p_k\}}{\min(\max_{u\in S}(f_{u,0}),\max_{u\in S}(f_{u,1}))}$$

既有min又有max，不是很好算。考虑min-max容斥，则答案为

$$\sum_S{\max_{u\in S}(f_{u,0})}+\sum_S{\max_{u\in S}(f_{u,1})}-\sum_S{\max_{u\in S}(\max(f_{u,0},f_{u,1}))}$$

注意到三者完全等价，我们只考虑第一项。

考虑将 $u$ 按 $f_{u,0}$ 升序排序后依次扫，那么问题转化为：

每次往某个组加入一个点，求从每个组中各选出一个点的方案数。

预处理逆元，容易做到线性复杂度。