I'm studying for TÜBTİAK's second step of Middle-School Competitive Programming branch, which is OI-style. I have translated the problem statement into English, keeping all Turkish proper names.

In the cute town of Ilgınkent, there are $$$n$$$ regions and are connected by $$$n-1$$$ roads, forming a tree-like structure. The distance between a region and all of its neighbors† is equal to 1 unit.

The mayor, Ms Kaya, has decided that it would make certain tasks easier if she organizes the complicated tree structure into roads‡ of length $$$k$$$. Ms Kaya wants you to design an algorithm to determine, for a given $$$k$$$ and a tree $$$T$$$, whether it is possible to split up $$$T$$$ into roads of length $$$k$$$.

  1
  |
2-3-4-6
  |
  5

examples of roads of length 2 are 1-3-5, 2-3-4, and 3-4-5, but not 1-3-6, 2-3-6. An edge may not be in two roads at the same time, making 1-2-3, 2-3-4; 2-3-4, 3-4-6 etc. invalid.

Input.

The first line contains the integer $$$n$$$. The next $$$n-1$$$ lines contain a description of Ilgınkent, where the line "u v" (w/o the quotes) means that there is a road between region $$$u$$$ and region $$$v$$$.

Output.

The output should be a single line — a bit array made of $$$0$$$ and $$$1$$$. For every $$$k$$$ output $$$1$$$ if the tree can be split up into roads of length $$$k$$$ and $$$0$$$ otherwise, left to right.

Constraints.

• $$$2 \le n \le 10^{5}$$$
• $$$1 \le k \le n-1$$$
• $$$1 \le u, v \le n$$$

//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define pb push_back

const int MAX = 1e5+5;

int N, sz[MAX], cur[MAX];

vector<int> adjlist[MAX], num[MAX];

bool bad = 0;
 
void dfs(int a, int b) {
    sz[a] = 1;
    for(int& t: adjlist[a]) 
     if (t != b) {
        dfs(t,a);
        sz[a] += sz[t];
        num[a].pb(sz[t]);
     }
    if (sz[a] != N) 
        num[a].pb(N-sz[a]);
}

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 count = 0;
        for (int& t: num[i]) {
            int z = t % K; 
            if (z == 0) continue;
            if (cur[K-z]) {
                cur[K-z]--; 
                count--;
            }
            else {
                cur[z]++; 
                count++;
            }
        }
        if (count) 
            return 0; 
    }
    return 1;
}
 
int main() {
    cin >> N;

    for (int i = 1; i < N; ++i) {
        int a,b; cin >> a >> b;
        adjlist[a].pb(b); 
        adjlist[b].pb(a);
    }

    dfs(1,0);

    for (int i = 1; i < N; ++i) {
        if (ok(i)) cout << 1;
        else cout << 0;
    }
    cout << endl;
}