A978. Delegation--Platinum
编程题
省选/NOI-
知识点
题目描述
Farmer John's farm consists of $N$ pastures ($2 \leq N \leq 10^5$) connected
by $N-1$ roads, so that any pasture is reachable from any other pasture. That
is, the farm is a tree. But after 28 years of dealing with the tricky
algorithmic problems that inevitably arise from trees, FJ has decided that a
farm in the shape of a tree is just too complex. He believes that algorithmic
problems are simpler on paths.
Thus, his plan is to partition the set of roads into several paths, and
delegate responsibility for each path to a worthy farm hand. To avoid
contention, he wants each path to be the same length. He wonders for which
lengths there exists such a partition.
More precisely, for each $1 \leq K \leq N-1$, help Farmer John determine
whether the roads can be partitioned into paths of length exactly $K$.
by $N-1$ roads, so that any pasture is reachable from any other pasture. That
is, the farm is a tree. But after 28 years of dealing with the tricky
algorithmic problems that inevitably arise from trees, FJ has decided that a
farm in the shape of a tree is just too complex. He believes that algorithmic
problems are simpler on paths.
Thus, his plan is to partition the set of roads into several paths, and
delegate responsibility for each path to a worthy farm hand. To avoid
contention, he wants each path to be the same length. He wonders for which
lengths there exists such a partition.
More precisely, for each $1 \leq K \leq N-1$, help Farmer John determine
whether the roads can be partitioned into paths of length exactly $K$.
输入格式
* In test cases 2-4 the tree forms a star; at most one vertex has degree greater than two.
* Test cases 5-8 satisfy $N\le 10^3$.
* Test cases 9-15 satisfy no additional constraints..
* Test cases 5-8 satisfy $N\le 10^3$.
* Test cases 9-15 satisfy no additional constraints..
输出格式
The first line contains a single integer $N$.
The next $N-1$ lines each contain two space-separated integers $a$ and $b$
describing an edge between vertices $a$ and $b$. Each of $a$ and $b$ is in the
range $1 \ldots N$.
The next $N-1$ lines each contain two space-separated integers $a$ and $b$
describing an edge between vertices $a$ and $b$. Each of $a$ and $b$ is in the
range $1 \ldots N$.
输入输出样例
输入 #1
Output a bit string of length $N-1.$ For each $1\le K\le N-1,$ the $K$th bit of this string from the left should equal one if it is possible to partition the edges of the tree into paths of length exactly $K$ and $0$ otherwise.
输出 #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
It is possible to partition this tree into paths of length $K$ for $K=1,2,3.$
It is possible to partition this tree into paths of length $K$ for $K=1,2,3.$