[CF526G] Spiders Evil Plan

给定一棵无根树，在树上选 $k$ 条路径，它们的并构成一个包含 $u$ 的连通块，要使连通块中包含的边的权值和最大。

一道纯粹的性质题。

首先，一棵树能够被 $k$ 条链覆盖，当且仅当它有不超过 $2k$ 个叶子。

这里必要性是显然的，至于充分性，构造任意一种所有叶子都被覆盖，每条边长度至少为 $1$ 的方案，如果树没有被完全覆盖，找出任意一条极长的没有一条边被覆盖的非空路径 $p$。显然 $p$ 的端点 $u,v$ 不为叶子，因为端点为叶子，意味着路径 $p$ 包含了叶子的唯一出边；而方案中所有叶子都被覆盖，意味着叶子的唯一连边也被覆盖，这与 $p$ 的要求矛盾。既然 $u,v$ 不为叶子，而 $p$ 极长，那么 $u,v$ 一定分别存在于两条覆盖路径 $s\to t,x\to y$ 上。此时我们调整方案，将这两条路径换成 $s\to x,t\to y$，原来被覆盖的所有边仍然被覆盖，而为被覆盖的路径 $p$ 被覆盖。因此我们不断进行这样的调整，这个过程一定会在有限步内结束。

其次，选择 $k$ 条链，构成的包含边权和最大的子图，一定是连通的。一个不连通的方案，通过上述调整方法可以使其变得连通，并且更优。也即我们只需要保证我们能够考虑到最优方案，并不需要注意我们是否考虑到了不连通的选链方案。

---

不难发现，包含边权和最大的连通块至少包含带权直径的端点中的一个，调整法易得。

鉴于正权树的带权直径的两个端点一定是叶子，问题形式变为，分别在以两个端点为根的树中，选择 $2k-1$ 个叶子，要求它们到根的路径的并形成的连通块包含 $u$，求连通块内边权和最大值。

抛开连通块包含 $u$ 的条件，进行一个简单的贪心——长链剖分（注意这里是划分边集，可能有出现在多个链中，而非像大多数树链剖分一样划分点集），然后选择最长的 $2k-1$ 条链构成该连通块。它的正确性也很显然，最优解必然可以表示为几个长链的并，否则一定存在某个长链，该方案只包含了这个长链的某个真子集，那么此时将这个长链并入该方案，不会使其产生新的叶子，却会使该方案的答案增加。每个长链恰含有一个叶子，也即我们能够选择最多 $2k-1$ 条长链。所以选择长度最长的 $2k-1$ 条长链一定不劣。

如果这样构造出来的方案不包含 $u$ 呢？我们需要做出一些调整。

第一种调整方法是只选长度最长的 $2k-2$ 条链，外加一条根到 $u$，再到 $u$ 子树内深度最大点的路径。

第二种调整方法是将 $u$ 的最近的在连通块内的祖先 $f$，不选 $f$ 以及它所在的长链中 $f$ 以下的部分，而是选择 $f$ 到 $u$，再到 $u$ 子树内深度最大点的路径。