C. 树的切割 详细题解

题目核心理解

给定一棵 $n$ 个结点的树，需要恰好删除 $k$ 条边，使整棵树分成 $k+1$ 个连通块。 求最大的 $x$，使得每个连通块的大小都不小于 $x$。

核心思路

1. 关键性质

• 答案具有单调性：若 $x$ 可行，则所有小于等于 $x$ 的值都一定可行。
• 因此可以对答案 $x$ 进行二分查找。
• 以任意结点为根进行贪心切割，最终能切出的合法块数量相同。

2. 判定规则

对给定的 $x$，用 DFS 后序遍历统计子树大小：

• 若某棵子树结点数 $\ge x$，则立即切断该子树与其父结点的边。
• 统计最多能切出多少个大小 $\ge x$ 的连通块。
• 若块数 $\ge k+1$，则 $x$ 可行，否则不可行。

算法流程

1. 二分答案范围：左端点 $l=1$，右端点 $r=\dfrac{n}{k+1}$。
2. 对当前二分值 $mid$，用 DFS 贪心计算最多可切分的块数。
3. 若块数足够，记录答案并尝试更大值；否则尝试更小值。
4. 二分结束后输出最大可行 $x$。

公式与复杂度分析

判定条件：

复杂度

• 二分次数：$O(\log n)$
• 单次判定 DFS：$O(n)$
• 总时间复杂度：$O(n \log n)$

可轻松处理 $n \le 10^5$、多组数据 $\sum n \le 10^5$ 的范围。