#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > graph;
vector<bool> tilt, vis;
vector<int> listVis;
int kezdo, db = 0;
void clearVis(){
for (int x : listVis) vis[x] = false;
listVis.clear();
}
int dfs (int pos){
vis[pos] = true;
listVis.push_back(pos);
int res = 1;
for (int x : graph[pos]){
if (tilt[x] || vis[x]) continue;
res += dfs(x);
}
if (res >= (db + 1) / 2 && kezdo == -1) kezdo = pos;
return res;
}
int kozep(int pos){
db = dfs(pos);
clearVis();
kezdo = -1;
dfs(pos);
clearVis();
if (kezdo == -1) kezdo = pos;
return kezdo;
}
int maxTav;
void dfs2(int pos, int tav){
vis[pos] = true;
listVis.push_back(pos);
maxTav = max(maxTav, tav);
for (int x : graph[pos]){
if (vis[x] || tilt[x]) continue;
dfs2(x, tav + 1);
}
}
vector<int> childs;
int dfs3(int pos, int tav){
vis[pos] = true;
listVis.push_back(pos);
int res = 1;
for (int x : graph[pos]){
if (vis[x] || tilt[x]) continue;
res += dfs3(x, tav + 1);
}
childs[tav] = max (childs[tav], res - 1);
return res;
}
vector<int> mo;
void centroid (int pos){
pos = kozep(pos);
// cout << pos << endl;
tilt[pos] = true;
vector<int> sor;
sor.push_back(0);
for (int x : graph[pos]){
if (tilt[x]) continue;
maxTav = -1;
dfs2(x, 1);
clearVis();
childs.assign(maxTav + 1, 0);
dfs3(x, 1);
clearVis();
childs[0] = dfs(x);
clearVis();
int ind = 0;
// cout << pos << ": " << x << ": ";
// for (int x : childs) cout << x << " ";
// cout << endl;
// for (int x : sor) cout << x << " ";
// cout << endl;
for (int i = 0; i < sor.size(); i++){
while (ind < childs.size() && childs[ind] > sor[i]) ind++;
if (ind == childs.size()) break;
mo[1 + ind + i] = max(mo[1 + ind + i], childs[ind]);
}
for (int i = 0; i < childs.size(); i++){
if (i == sor.size()) sor.push_back(childs[i]);
sor[i] = max(sor[i], childs[i]);
}
}
// cout << "MO: " << pos << ": ";
// for (int x : mo) cout << x << " ";
// cout << endl;
sor.clear();
sor.push_back(0);
reverse(graph[pos].begin(), graph[pos].end());
for (int x : graph[pos]){
if (tilt[x]) continue;
maxTav = -1;
dfs2(x, 1);
clearVis();
childs.assign(maxTav + 1, 0);
dfs3(x, 1);
clearVis();
childs[0] = dfs(x);
clearVis();
int ind = 0;
// cout << pos << ": " << x << ": ";
// for (int x : childs) cout << x << " ";
// cout << endl;
// for (int x : sor) cout << x << " ";
// cout << endl;
for (int i = 0; i < sor.size(); i++){
while (ind < childs.size() && childs[ind] > sor[i]) ind++;
if (ind == childs.size()) break;
mo[1 + ind + i] = max(mo[1 + ind + i], childs[ind]);
}
for (int i = 0; i < childs.size(); i++){
if (i == sor.size()) sor.push_back(childs[i]);
sor[i] = max(sor[i], childs[i]);
}
}
// cout << "MO: " << pos << ": ";
// for (int x : mo) cout << x << " ";
// cout << endl;
for (int x : graph[pos]){
if (tilt[x] == false){
centroid(x);
}
}
}
int main(){
int n;
cin >> n;
graph.resize(n);
for (int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
a--, b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
mo.assign(n + 1, -1);
vis.assign(n, false);
tilt.assign(n, false);
centroid(0);
for (int i = n - 3; i >= 0; i--){
if (mo[i + 2] != -1) mo[i] = max(mo[i], mo[i + 2] + 1);
}
// for (int x : mo){
// cout << x << " ";
// }
// cout << endl;
int ind = n;
for (int i = 1; i <= n; i++){
if (i % 2 == 1) {
cout << 1 << '\n';
continue;
}
while (ind > 0 && (mo[ind] + 1) * 2 < i) ind--;
cout << ind << '\n';
}
return 0;
}
/*
5
1 2
2 3
4 2
3 5
*/
Compilation message
meetings2.cpp: In function 'void centroid(int)':
meetings2.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = 0; i < sor.size(); i++){
| ~~^~~~~~~~~~~~
meetings2.cpp:86:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | while (ind < childs.size() && childs[ind] > sor[i]) ind++;
| ~~~~^~~~~~~~~~~~~~~
meetings2.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | if (ind == childs.size()) break;
| ~~~~^~~~~~~~~~~~~~~~
meetings2.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < childs.size(); i++){
| ~~^~~~~~~~~~~~~~~
meetings2.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if (i == sor.size()) sor.push_back(childs[i]);
| ~~^~~~~~~~~~~~~
meetings2.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int i = 0; i < sor.size(); i++){
| ~~^~~~~~~~~~~~
meetings2.cpp:120:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | while (ind < childs.size() && childs[ind] > sor[i]) ind++;
| ~~~~^~~~~~~~~~~~~~~
meetings2.cpp:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | if (ind == childs.size()) break;
| ~~~~^~~~~~~~~~~~~~~~
meetings2.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 0; i < childs.size(); i++){
| ~~^~~~~~~~~~~~~~~
meetings2.cpp:125:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | if (i == sor.size()) sor.push_back(childs[i]);
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
