[USACO20FEB] Delegation G
题目描述
Farmer John 有 $N$ 个牧场,这些牧场通过 $N-1$ 条道路连接,形成了一个树形结构。
但在 28 年的经营后(译者注:USACO 创办于 1992 年),FJ 觉得处理树上问题非常辣手,他认为一条链上的问题更加简单。
因此他决定将整棵树划分为若干条链,将每一条链的管理权授予一位工人。为了避免可能的争端,他希望所有链的长度均相同。
FJ 现在想知道,对于每一个满足 $1 \leq K \leq N-1$ 的 $K$,是否存在一种划分方案,使得整棵树被划分成若干条链,且每条链的长度都**恰好**是 $K$。
输入输出格式
输入格式
第一行一个整数 $N$($1 \leq N \leq 10^5$)。
接下来 $N-1$ 行,每行两个整数 $u,v$($1 \leq u,v \leq N$),描述一条连接 $u,v$ 的道路。
输出格式
输出一个长度 $N-1$ 的 0/1 串。第 $i$ 位的值为 $1$ 当且仅当存在一种划分方案,使得整棵树被划分成若干条链,且每条链的长度都恰好是 $i$,否则第 $i$ 位的值为 $0$。
输入输出样例
输入样例 #1
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
输出样例 #1
111000000000
说明
### 样例解释
$K=1,2,3$ 时都存在一种合法的划分方案。
$K=3$ 时的一种划分方案如下:
$13-12-11-8, 10-9-8-6, 7-6-2-3, 5-4-2-1$
### 子任务
- 测试点 $2 \sim 4$ 满足**最多**有一个点的度数大于 $2$。
- 测试点 $5 \sim 8$ 满足 $N \leq 10^3$。
- 测试点 $9 \sim 15$ 没有特殊限制。