#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> adjlst[200100];
int u,v;
int suff[200100];
bool used[200100];
int tparent[200100];
int tsise[200100];
int sise[200100];
int parent[200100];
int d[200100];
void tfs(int i, int p){
tparent[i] = p;
tsise[i] = 1;
for(int j : adjlst[i]){
if(j == p) continue;
tfs(j,i);
tsise[i] += tsise[j];
}
}
void dfs(int i, int p){
sise[i] = 1;
parent[i] = p;
for(int j : adjlst[i]){
if(j == p || used[j]) continue;
dfs(j,i);
sise[i] += sise[j];
}
}
void loadfs(int i, int p, int de, vector<int> &a){
if(de == a.size()){
a.push_back(0);
}
for(int j : adjlst[i]){
if(j == p || used[j]) continue;
loadfs(j,i, de + 1, a);
}
if(tparent[i] == p){
a[de] = max(a[de], tsise[i]);
}
else{
a[de] = max(a[de],N - tsise[p]);
}
}
void solve(int i){
int c = i;
dfs(i,-1);
while(true){
bool die = true;
for(int j : adjlst[c]){
if(j == parent[c] || used[j]) continue;
if(sise[j] * 2 >= sise[i]){
c = j;
die = false;
break;
}
}
if(die) break;
}
used[c] = true;
vector<pair<int,int>> v = {{N,N}};
vector<int> pros;
for(int j : adjlst[c]){
if(used[j]) continue;
int num;
if(tparent[j] == c){
num = N - tsise[j];
}
else{
num = tsise[c];
}
vector<int> temp = {N};
loadfs(j,c,1,temp);
for(int i = 1; i < temp.size(); i++){
if(v.size() == i) v.push_back({0,0});
v[i] = max(max(v[i],{temp[i],v[i].first}), {v[i].first,temp[i]});
suff[i] = max(suff[i], min(temp[i], num) );
}
}
for(pair<int,int> ii : v) pros.push_back(ii.first);
for(int j : adjlst[c]){
if(used[j]) continue;
vector<int> temp = {N};
loadfs(j,c,1,temp);
for(int i = 1; i < temp.size(); i++){
if(v[i].first == temp[i]){
if(v[i].second == 0) pros.pop_back();
}
else{
pros[i] = v[i].second;
}
}
if(!pros.empty()){
for(int i = 1; i < temp.size(); i++){
if(pros[0] >= temp[i]){
auto it = upper_bound(pros.begin(),pros.end(),temp[i],greater<int>());
suff[i + (it - pros.begin() - 1)] = max(suff[i + (it - pros.begin() - 1)], temp[i]);
}
}
}
}
/*printf("%d\n",c);
for(int i = 0; i <= N; i++){
printf("%d ",suff[i]);
}
printf("\n");*/
for(int j : adjlst[c]){
if(!used[j]) solve(j);
}
}
int main(){
scanf(" %d",&N);
for(int i = 0; i < N - 1; i++){
scanf(" %d",&u);
scanf(" %d",&v);
adjlst[u].push_back(v);
adjlst[v].push_back(u);
}
for(int i = 0; i <= N; i++){
suff[i] = 0;
used[i] = false;
}
suff[0] = N;
tfs(1,-1);
solve(1);
for(int i = N - 1; i >= 0; i--){
suff[i] = max(suff[i + 1],suff[i]);
}
int it = N;
for(int i = 1; i <= N; i++){
if(i % 2 == 1){
printf("1\n");
}
else{
while(suff[it] < i/2) it--;
printf("%d\n",it + 1);
}
}
}
/*
4
1 2
3 2
4 3
7
1 2
2 3
3 4
4 5
2 6
3 7
6
1 2
2 3
2 4
4 5
4 6
*/
컴파일 시 표준 에러 (stderr) 메시지
meetings2.cpp: In function 'int main()':
meetings2.cpp:145:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
145 | scanf(" %d",&N);
| ~~~~~^~~~~~~~~~
meetings2.cpp:148:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | scanf(" %d",&u);
| ~~~~~^~~~~~~~~~
meetings2.cpp:149:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | scanf(" %d",&v);
| ~~~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |