#P5579. [Usaco2020 Feb]Delegation
[Usaco2020 Feb]Delegation
[USACO20FEB] Delegation G
题目描述
Farmer John 有 个牧场,这些牧场通过 条道路连接,形成了一个树形结构。
但在 28 年的经营后(译者注:USACO 创办于 1992 年),FJ 觉得处理树上问题非常辣手,他认为一条链上的问题更加简单。
将所有道路划分成若干条简单路径。每条道路恰好属于一条路径,不同路径可以经过同一个牧场。路径的长度等于其包含的道路数。
对每个 (),判断是否存在一种划分,使每条路径的长度恰好为 。
输入格式
第一行一个整数 ()。
接下来 行,每行两个整数 (),描述一条连接 的道路。
输出格式
输出一个长度 的 0/1 串。第 位的值为 当且仅当存在一种划分方案,使得整棵树被划分成若干条链,且每条链的长度都恰好是 ,否则第 位的值为 。
样例 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
111000000000
提示
样例解释
时都存在一种合法的划分方案。
时的一种划分方案如下:
子任务
- 测试点 满足最多有一个点的度数大于 。
- 测试点 满足 。
- 测试点 没有特殊限制。