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.↵
<hr>↵
Time limit: 1 s, memory limit, 64 MB↵
↵
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$.↵
<hr>↵
† A region is another region's neighbor iff there exists a path between the two regions with no other region within said path.↵
<hr>↵
‡ A road is a collection of edges which forms a continuous path. For example, in the tree↵
↵
~~~~~plaintext↵
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$↵
↵
<spoiler summary="Or, you can help me understand the code provided">↵
↵
~~~~~cpp↵
//#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,altsz[MAX], cur[MAX];↵
↵
vector<int> adjlist[MAX], num[MAX];↵
↵
bool bad = 0;↵
↵
void dfs(int a, int b) {↵
altsz[a] = 1;↵
for(int& t: adjlist[a]) ↵
if (t != b) {↵
dfs(t,a);↵
altsz[a] += altsz[t];↵
num[a].pb(altsz[t]);↵
}↵
if (altsz[a] != N) ↵
num[a].pb(N-altsz[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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<hr>↵
Time limit: 1 s, memory limit, 64 MB↵
↵
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$.↵
<hr>↵
† A region is another region's neighbor iff there exists a path between the two regions with no other region within said path.↵
<hr>↵
‡ A road is a collection of edges which forms a continuous path. For example, in the tree↵
↵
~~~~~plaintext↵
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$↵
↵
<spoiler summary="Or, you can help me understand the code provided">↵
↵
~~~~~cpp↵
//#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,
↵
vector<int> adjlist[MAX], num[MAX];↵
↵
bool bad = 0;↵
↵
void dfs(int a, int b) {↵
for(int& t: adjlist[a]) ↵
if (t != b) {↵
dfs(t,a);↵
num[a].pb(
}↵
if (
num[a].pb(N-
}↵
↵
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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
