算法思路

这是一个 二分答案 + 贪心匹配 的树上问题。

核心思想

二分可能的 $K$ 值，检查是否能够将整棵树的边划分成若干长度至少为 $K$ 的路径。

检查函数 check()

对于给定的 $MID$（即尝试的 $K$ 值），从叶子向根（DFS 后序）处理每个节点：

状态定义

• mx[x]：表示在 $x$ 的子树中，从 $x$ 向下延伸的一条未匹配完成的路径长度（如果为 0 表示没有未匹配路径）。
• 目标是在每个节点处，将子节点传上来的路径两两配对，使得每条配对路径长度之和 $\ge MID$。

关键过程

1. 叶子节点：mx[x] = 0（没有向下延伸路径）。
2. 内部节点：
   • 收集所有子节点传上来的路径长度 v[i] = mx[child] + 1（加 1 是因为连接到当前节点的边）。
   • 对 v 排序，尝试贪心配对：
     • 尽量让短的路径和长的路径配对，使得和 $\ge MID$。
     • 如果某条路径无法配对，则可能作为向上延伸的路径（mx[x]）。
3. 根节点特殊处理：
   • 根节点没有父节点，所以必须将所有子节点传上来的路径完全配对，不能有剩余未匹配路径。
   • 如果根节点处无法完全配对，则 flag = 1 表示该 $MID$ 不可行。

贪心配对算法

在 pd(v) 函数中：

• 如果 v.size() 是奇数，先取出最后一个（最长的）作为可能的未匹配路径？
• 然后用双指针法：l 从左边开始，r 从右边开始，尽量让 v[l] + v[r] >= MID。
• 如果发现某对和 < MID，则配对失败。

在 DFS 中的二分部分：

• 实际上是尝试选择哪一条路径作为向上延伸的（不参与当前节点配对）。
• 二分选择保留的路径下标，检查剩下的能否全部配对成功。

二分框架

• 下界 l = 1，上界 r = n。
• 如果 check(MID) 返回 true（即 !flag），说明 $K = MID$ 可行，尝试更大的值。
• 否则减小 $K$。

最后输出最大的可行 $r$。

复杂度

• 二分：$O(\log n)$
• 每次检查：$O(n \log n)$（每个节点排序和双指针/二分）
• 总复杂度：$O(n \log^2 n)$

代码要点总结

1. 二分答案：找最大的 $K$。
2. 树上后序处理：从叶子到根，每个节点处理子节点传上来的路径。
3. 贪心配对：用双指针法尽量让短路径和长路径配对，满足长度和 $\ge K$。
4. 根节点特殊判断：根节点必须完全配对，不能有剩余未匹配路径。
5. mx[x] 设计：表示向上延伸的未匹配路径长度，用于父节点继续配对。