#P5579. [Usaco2020 Feb]Delegation

    ID: 4580 传统题 1000ms 256MiB 尝试: 11 已通过: 5 难度: 6 上传者: 标签>难度分类提高动态规划树形 DP状态维度消除模拟与实现技巧稀疏状态重置CF2100

[Usaco2020 Feb]Delegation

[USACO20FEB] Delegation G

题目描述

Farmer John 有 NN 个牧场,这些牧场通过 N−1N-1 条道路连接,形成了一个树形结构。

但在 28 年的经营后(译者注:USACO 创办于 1992 年),FJ 觉得处理树上问题非常辣手,他认为一条链上的问题更加简单。

将所有道路划分成若干条简单路径。每条道路恰好属于一条路径,不同路径可以经过同一个牧场。路径的长度等于其包含的道路数。

对每个 KK(1≤K≤N−11\le K\le N-1),判断是否存在一种划分,使每条路径的长度恰好为 KK。

输入格式

第一行一个整数 NN(2≤N≤1052\le N\le 10^5)。

接下来 N−1N-1 行,每行两个整数 u,vu,v(1≤u,v≤N1 \leq u,v \leq N),描述一条连接 u,vu,v 的道路。

输出格式

输出一个长度 N−1N-1 的 0/1 串。第 ii 位的值为 11 当且仅当存在一种划分方案,使得整棵树被划分成若干条链,且每条链的长度都恰好是 ii,否则第 ii 位的值为 00。

样例 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

提示

样例解释

K=1,2,3K=1,2,3 时都存在一种合法的划分方案。

K=3K=3 时的一种划分方案如下:

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

子任务

  • 测试点 2∼42 \sim 4 满足最多有一个点的度数大于 22。
  • 测试点 5∼85 \sim 8 满足 N≤103N \leq 10^3。
  • 测试点 9∼159 \sim 15 没有特殊限制。