CF1179D题解

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

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

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

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

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

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

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

将上式展开，有

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

然后就做完了。