CF1039D You Are Given a Tree

题意

给定一棵有 个节点的树. 对于满足 的每一个 ，把树分成若干条包含 个顶点的链，其中每个点最多属于一条链，问最多能分得几条链

题解

考虑 固定时怎么做

贪心
对于一个点，如果在它的子树内有一条经过该点且不经过以被使用点的链，那么将这条链计入答案并将该点标记为使用过

简单的证明：
对于点 满足在其子树内有一条经过该点且不经过以被使用点的链，如果这条链不计入答案，而是选取一条经过 的但不全在 子树中的链，这样划分的链数不会增加，还会占用点 子树外的点

令 表示 时的答案，显然有

类似除法分块， 一共只有 种取值

因此对于每一种取值二分右端点，时间复杂度为 ，不足以通过此题

考虑对前 项直接暴力，只对后面的 种取值二分

时间复杂度为 ， 取 时有最优复杂度

代码 codeforces submission 144337474