CF1039D You Are Given a Tree

题意：给出一棵 个节点的树。

对于 ，分别求：选择点不相交的长为 的若干简单路径，最多能选多少条。

，时限 。

---

首先思考如何对指定的 求解。

贪心：从深往浅考虑，若能在子树内合成一条链则尽量合成。

具体实现 ：

维护子树内还能向下延伸的最长链长度 。

将儿子中 的最大值和次大值合并，若可以拼成符合要求的链，则拼接，并将 置为 ，否则继承儿子的最大值。

---

若要对所有 求解，使用根号分治。

设一个阈值 。

对于 的部分，暴力求解，复杂度为 。

对于 的部分，显然答案 ，而答案又是单调不增的，所以分为了 个段。

可以二分出每个段的具体位置，复杂度为 。

综上，令 即可得复杂度 。