CF526G Spiders Evil Plan

题意：给定一棵 个点的无根树，每条边有边权。

有 次询问，每次给出 ，需要选择 条树上的路径，使这些路径形成一个包含点 的连通块，且连通块中包含的边权和最大。

强制在线，，边权均为正，时限 。

---

先考虑单组询问。

• 定理：树有不超过 个叶子 可以被 条路径覆盖。

  必要性显然，下证充分性。

  以叶子为权，选取重心为根，可以保证每个分支内部都有不超过 个叶子。

  将这些叶子匹配起来，让每条路径都经过根。

  现在，对于每个叶子，其到根的路径都被覆盖过，显然整棵树都被覆盖了。

现在，以点 为根，问题等价于选取 个叶子是的向上的路径并最大。(注意根也可能是叶子)

这等价于带权长剖后选择长度前 (或者 )的长链。

---

接下来考虑多组询问。

能够发现，无论以何点为根，最长的长链端点必然可以是直径的端点。也就是说，选出的树形图必然包含直径的端点之一。

所以，我们只需要考虑根为直径端点的情况。

选出前 (直径端点必然是叶子) 的长链后，可能并不包含点 ，需要做些调整。

设 子树内最深点为 。

有如下两种方案：

• 去掉第 条长链，然后将 到根的路径加入树形图。

• 找到 被包含在树形图内的最深祖先，将所在长链的后半段切掉。

容易使用倍增实现。

复杂度 。