3367. [USACO20 Feb Gold]Delegation(Gold)

【题目描述】

Farmer John 的农场由 $N$ 块草地（$1 \leq N \leq 10^5$）和 $N-1$ 条道路组成，满足每块草地都能从任意其他草地到达。也就是说，这个农场组成一棵树。但在与不可避免地由树而生的麻烦的算法问题打了 28 年交道之后，FJ 终于认为树形的农场太复杂了。他相信在链上的算法问题更简单。

所以，他的计划是将这些道路划分成若干条链，并将每条链交给一名值得信任的农场工人负责。为了避免争执，他希望每条链的长度相同。他想知道对于哪些长度存在这样的划分。

更具体地，对于每个 $1 \leq K \leq N-1$，帮助 Farmer John 求出这些道路是否能被划分为长度恰好为 $K$ 的链。

【输入格式】

第一行包含一个整数 $N$。

以下 $N-1$ 行每行包含两个空格分隔的整数 $a$ 和 $b$，表示结点 $a$ 与 $b$ 之间有一条边。$a$ 和 $b$ 均在范围 $1 \ldots N$ 内。

【输出格式】

输出一个长为 $N-1$ 的二进制字符串。对于每一个 $1\le K\le N-1$，如果可以将树的边划分为长度恰好为 $K$ 的链，则字符串从左往右数第 $K$ 位为 $1$，否则为 $0$。

【样例输入】

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

【样例输出】

111000000000

【样例解释】

对于 $K=1,2,3$，有可能将树划分为长为 $K$ 的链。对于 $K=3$，一种可能的划分方式如下：

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

【提示】

对于$ 20\% $的测试数据(测试点$ 2 \sim 4 $)，树组成了一个 “星形”，即至多一个结点的度大于二。 

另有$ 27\% $的测试数据(测试点$ 5 \sim 8 $)，满足$ N\le 10^3 $。 

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。