给定树可将k的哪些值分解为长度为k的不相交的路径？

Question

所以曾有人问过这个问题，但是它被删除了。

给出一棵树，它可以将k的哪些值分解为长度为k的不相交的路径？

根据树的定义，该树具有N个节点和N-1个边。

对于每个1 <= k <= N-1，确定是否有可能将树分解为长度为k的不相交的路径。

解决方案应该是O（N ^ 2），或者甚至更好的O（N log N）或O（N）-我不确定复杂度是多少。

Answer 1

您可以使用以下贪婪算法，并且时间复杂度为[[O（n log n）：]]

选择一个完全具有一个邻居的根
1. R

。虽然还剩下任何节点：

选择距
• R
最远的叶子L。 （可能有最远的一个。选择其中的任何一个。）

从树中删除包含

L

的长度k的路径P。如果存在多个这样的路径，请选择不位于L到R的路径上的任何路径。如果存在孤立节点（没有父节点的非根节点，或者等效的-没有到[[R的路径]），则无法分解。 return false

此时，图为空，我们发现了分解。 return true