将树划分为k个长度的路径

Question

问题是，您有一个具有N个节点（1 <= N <= 10 ^ 5）的树，您试图将其划分为路径。每个路径必须具有相同的长度。对于每个k（0 <= K <= N-1），您试图确定是否可以将树划分为长度为k的路径。路径必须是唯一的。

示例。对于13个节点的树，这些是边：

1 2
2 3
2 4
4 5
2 6
6 7
6 8
8 9
9 10
8 11
11 12
12 13

解决方案是，可以将这棵树划分为K = 1,2,3的长度为K的路径。对于K = 3，可能的一组路径如下：

13-12-11-8、10-9-8-6、7-6-2-3、5-4-2-1

我对此问题的第一个观察结果是，您仅应测试某些长度K，以使（N-1）被K整除。也不应检查任何K，以使K>（N-1）/ 2。我已经看到了几种解决方案，但是对于非唯一路径以及可以重新访问节点的路径。如何解决此问题，而无需强行使用？

Answer 1

这似乎是一个TreeDP问题。使用dfs。对于每个节点，存储边数mod k。遍历节点的所有子节点，并将边缘i> 0的子节点与边缘k-i的子节点匹配。如果有多个不匹配的孩子，则无法使用此k值。

USACO祝你好运：）