#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);
db = dfs(pos);
clearVis();
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) - 1;
sor[0] = db - childs[0] - 2;
clearVis();
int ind = 1;
// 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;
if (i < sor.size() - 1){
while (childs[ind] > sor[i + 1]){
mo[1 + ind + i] = max(mo[1 + ind + i], childs[ind]);
ind++;
}
}
else 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());
db = dfs(pos);
clearVis();
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) - 1;
sor[0] = db - childs[0] - 2;
clearVis();
int ind = 1;
// 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;
if (i < sor.size() - 1){
while (childs[ind] > sor[i + 1]){
mo[1 + ind + i] = max(mo[1 + ind + i], childs[ind]);
ind++;
}
}
else 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:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < sor.size(); i++){
| ~~^~~~~~~~~~~~
meetings2.cpp:89:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | while (ind < childs.size() && childs[ind] > sor[i]) ind++;
| ~~~~^~~~~~~~~~~~~~~
meetings2.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | if (ind == childs.size()) break;
| ~~~~^~~~~~~~~~~~~~~~
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() - 1){
| ~~^~~~~~~~~~~~~~~~
meetings2.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int i = 0; i < childs.size(); i++){
| ~~^~~~~~~~~~~~~~~
meetings2.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | if (i == sor.size()) sor.push_back(childs[i]);
| ~~^~~~~~~~~~~~~
meetings2.cpp:131:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 0; i < sor.size(); i++){
| ~~^~~~~~~~~~~~
meetings2.cpp:132:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | while (ind < childs.size() && childs[ind] > sor[i]) ind++;
| ~~~~^~~~~~~~~~~~~~~
meetings2.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | if (ind == childs.size()) break;
| ~~~~^~~~~~~~~~~~~~~~
meetings2.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | if (i < sor.size() - 1){
| ~~^~~~~~~~~~~~~~~~
meetings2.cpp:142:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int i = 0; i < childs.size(); i++){
| ~~^~~~~~~~~~~~~~~
meetings2.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | 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 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
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 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
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 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
