CF1179D题解

· · 题解

先考虑一棵基环树上有多少条简单路径，设环上有 num 个点，环上第 i 个点的子树内共有 a_i 个点。有

\begin{aligned} ans &= \sum _{i=1} ^{num} \frac{1}{2} a_i \times (a_i -1)+(a_i \times (n-a_i)) \\ &=\frac{2n^2-n}{2}-\frac{1}{2}\sum _{i=1} ^{num} a_i^2 \end{aligned}

要最大化 ans ，就要最小化 \sum _{i=1} ^{num} a_i^2 ，记为 ret 。

在原树中，两个点之间连一条边，这条新边就和两个点之间的简单路径形成了一个环，我们称该路径被这条新边覆盖了。对于一个被覆盖的点它既不是叶子节点，也不是新边两端点的LCA，那么它一定能向下扩展一个节点直到叶子节点，使得答案更优，这不难理解。也就是说，连的新边的两个端点一定是树上的叶节点(度为1的点)。

令 f_i 表示从非 i 的子树中的一个点向 i 的子树中的一个点连边，只考虑 i 的子树造成的贡献的最小值，即此时点 u 一定被覆盖，且恰有一个儿子被覆盖。于是对于非叶子节点 u ，有

f_u=\min _v \{ f_v+(siz_u-siz_v)^2 \}

其中 siz_u 表示点 u 的子树大小。特别地，对于叶子节点 u ，有 f_u=1 。

有了 f 数组后，考虑如何合并答案，对于点 u ，当 u 为新边的两端点的LCA时，我们可以朴素地枚举 u 的两个儿子 x 和 y ，表示两端点分别在 x 和 y 的子树内，此时的贡献为

ret=f_x+f_y+(n-siz_x-siz_y)^2

这样做的时间复杂度是 O(n^2) 的，不能通过。

将上式展开，有

ret=n^2+f_x-2nsiz_x+siz_x^2+f_y-2nsiz_y+siz_y^2+2siz_xsiz_y

发现可以套用斜率优化。具体地，将点 u 的儿子按 siz 从小到大排序，枚举 x ，用单调队列维护一个下凸壳 。

然后就做完了。