CF1039D You Are Given a Tree

题意

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

$n\le 10^5$

题解

考虑 $k$ 固定时怎么做

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

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

令 $f_i$ 表示 $k=i$ 时的答案，显然有 $f_i\le\lfloor\frac{n}{i}\rfloor$

类似除法分块，$f_i$ 一共只有 $\mathcal{O}(\sqrt{n})$ 种取值

因此对于每一种取值二分右端点，时间复杂度为 $\mathcal{O}(n\sqrt{n}\log n)$，不足以通过此题

考虑对前 $T$ 项直接暴力，只对后面的 $\mathcal{O}(\frac{n}{T})$ 种取值二分

时间复杂度为 $\mathcal{O}(nT+\frac{n}{T}\log n)$，$T$ 取 $\sqrt{n\log n}$ 时有最优复杂度 $\mathcal{O}(n\sqrt{n\log n})$

代码 codeforces submission 144337474