Delegation

题目描述

农夫约翰的农场由 $N$ 个牧场（$2 \leq N \leq 10^5$）组成，它们通过 $N-1$ 条道路连接，使得任意一个牧场都能到达任意另一个牧场。也就是说，这个农场是一棵树。但在处理了 28 年树上不可避免出现的棘手算法问题之后，FJ 决定树形的农场太复杂了。他认为路径上的算法问题更简单。 因此，他计划将这些道路划分成若干条路径，并把每条路径的管理交给一位合格的农场工人。为避免冲突，他希望每条路径的长度都相同。他想知道对于哪些长度，存在这样的划分。 更具体地，对于每个 $1 \leq K \leq N-1$，请帮助农夫约翰判断是否能将道路划分为长度恰好为 $K$ 的路径。

输入格式

第一行包含一个整数 $N$。 接下来的 $N-1$ 行每行包含两个用空格分隔的整数 $a$ 和 $b$，描述顶点 $a$ 与顶点 $b$ 之间的一条边。$a$ 和 $b$ 均在范围 $1 \ldots N$ 内。

输出格式

输出一个长度为 $N-1$ 的比特串。对于每个 $1\le K\le N-1$，该串从左往右的第 $K$ 位应为 1，当且仅当可以将树的边划分为长度恰好为 $K$ 的路径；否则为 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

提示

评分说明： 在测试点 2-4 中，树为星形；至多只有一个顶点的度数大于二。 测试点 5-8 满足 $N\le 10^3$。 测试点 9-15 没有额外限制。 可以将这棵树在 $K=1,2,3$ 时划分为长度为 $K$ 的路径。 当 $K=3$ 时，一种可行的路径集合如下：

题目贡献者：Mark Gordon 和 Dhruv Rohatgi

标签: USACO|2020|Gold

来源

USACO|2020|Gold