P6147 [USACO20FEB] Delegation G

Farmer John has $N$ pastures, connected by $N-1$ roads, forming a tree. But after 28 years of running the farm (translator's note: USACO was founded in 1992), FJ feels that dealing with tree problems is very troublesome, and he thinks problems on a single path are easier. So he decides to split the whole tree into several chains, and give the management of each chain to a worker. To avoid possible disputes, he wants all chains to have the same length. FJ now wants to know, for each $K$ satisfying $1 \leq K \leq N-1$, whether there exists a way to partition the entire tree into several chains such that every chain has length **exactly** $K$.

The first line contains an integer $N$ ($1 \leq N \leq 10^5$). The next $N-1$ lines each contain two integers $u, v$ ($1 \leq u, v \leq N$), describing a road connecting $u$ and $v$.

Output a 0/1 string of length $N-1$. The $i$-th character is $1$ if and only if there exists a partition plan such that the whole tree is partitioned into several chains and every chain has length exactly $i$; otherwise, the $i$-th character is $0$.

### Sample Explanation When $K = 1, 2, 3$, there is a valid partition plan. One valid partition plan for $K = 3$ is: $13-12-11-8, 10-9-8-6, 7-6-2-3, 5-4-2-1$ ### Subtasks - Test points $2 \sim 4$ satisfy that there is **at most** one node whose degree is greater than $2$. - Test points $5 \sim 8$ satisfy $N \leq 10^3$. - Test points $9 \sim 15$ have no special constraints. Translated by ChatGPT 5