(Analysis by Benjamin Qi)

Root the tree at $1$. We will do DP on subtrees.

First, observe that the answer is "no" if $N-1$ is not divisible by $K.$ Otherwise, we wish to write a function $dfs(x)$ which will check whether it is possible to partition the subtree corresponding to vertex $x$ into paths of length $K$ and possibly an extra one of length less than $K$ with one endpoint at $x$. If possible, this function will return the length of the extra path. Otherwise, the function will return $-1$.

First, we should call $dfs(t)$ for all children $t$ of $x.$ If any of these return $-1,$ then $dfs(x)$ should also return $-1.$ Otherwise, we have a path of length $dfs(t)+1$ with one endpoint at $x.$ After doing this, we should pair up as many of the paths whose lengths are in $(0,K)$ as possible. If there is more than one unpaired path remaining after this process, return $-1$.

Otherwise, return the length of the unpaired path, or zero if none exists. Note that if $dfs(x)\neq -1,$ then its return value is equal to the remainder when the number of edges in the subtree corresponding to $x$ is divided by $K,$ which is invariant regardless of how exactly we choose the paths of length $K$.

For a fixed $K,$ we can check whether it is possible to split the tree into paths of length $K$ in $O(N)$ time, allowing us to solve the problem in $O(N\cdot (\#\text{ of divisors of }N)).$ However, several solutions with this complexity ended up receiving TLE on test case $3$, where $N=83161$ and $N-1$ has $128$ divisors. One option is to deal with the star case separately. Another is to write a checker that does not use recursion and is a constant factor faster, demonstrated below.

#include "bits/stdc++.h"

using namespace std;

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 

#define f first
#define s second

const int MOD = 1e9+7;
const int MX = 1e5+5;

int N,sub[MX];
vector<int> adj[MX], num[MX];
bool bad = 0;
void dfs(int a, int b) {
	sub[a] = 1;
	for(auto& t: adj[a]) if (t != b) {
		sub[a] += sub[t];
	if (sub[a] != N) num[a].push_back(N-sub[a]);
int cur[MX]; // basically unordered map
bool ok(int K) {
	if ((N-1)%K != 0) return 0;
	for (int i = 0; i < K; ++i) cur[i] = 0;
	for (int i = 1; i <= N; ++i) {
		int cnt = 0;
		for (auto& t: num[i]) {
			int z = t%K; if (z == 0) continue;
			if (cur[K-z]) cur[K-z] --, cnt --;
			else cur[z] ++, cnt ++;
		if (cnt) return 0; // paths don't pair up
	return 1;
int main() {
	cin >> N;
	for (int i = 1; i < N; ++i) {
		int a,b; cin >> a >> b;
		adj[a].push_back(b), adj[b].push_back(a);
	for (int i = 1; i < N; ++i) {
		if (ok(i)) cout << 1;
		else cout << 0;
	cout << "\n";