3784

传送门 description 对于一个元素都 \(\leq n\) 的正整数集合 \(S\)（不含相同元素），\(f(i)\) 表示使用集合 \(S\) 里的数加和为 \(i\) 的方案数，每个元素可以被使用多次，两个方案不同当且仅当存在一个元素在两种方案中使用次数不同。 现给定 \(n\) 和 ......

# BZOJ #3784. 树上的路径 ## 题意 给一颗树，求所有路径长度中前 $k$ 大。 ## 题解 首先对于前 $k$ 大，我们有一个常见的方法，二分。 二分第 $k$ 大的路径长度，然后使用点分治统计，点分治内部还要二分，所以时间复杂度 $O(nolg^3n)$ 。 二分显然是行不通了，想 ......