This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;
struct dude{
int h,l;
};
int n,a,b,sz[MAXN],root,parent[MAXN],pt[MAXN],ans[MAXN];
int dist[MAXN],maxs;
vector<int> v[MAXN];
bool used[MAXN];
void dfs(int x,int p){
sz[x]=1; parent[x]=p;
for(int i=0;i<v[x].size();i++){
if(v[x][i]==p)continue;
dfs(v[x][i],x);
sz[x]+=sz[v[x][i]];
}
}
int centroid(int x,int p){
for(int i=0;i<v[x].size();i++){
if(v[x][i]==p)continue;
if(sz[v[x][i]]>n/2){
return centroid(v[x][i],x);
}
}
return x;
}
void dfs1(int x,int p,int d){
dist[x]=d;
for(int i=0;i<v[x].size();i++){
if(v[x][i]==p or used[v[x][i]])continue;
dfs1(v[x][i],x,d+1);
}
}
int diameter(){
for(int i=1;i<=n;i++){
if(used[i])continue;
dfs1(i,0,0); break;
}
maxs=0;
for(int i=1;i<=n;i++){
if(used[i])continue;
if(dist[i]>dist[maxs])maxs=i;
}
dfs1(maxs,0,0);
maxs=0;
for(int i=1;i<=n;i++){
if(used[i])continue;
maxs=max(maxs,dist[i]);
}
return maxs+1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n-1;i++){
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1,0);
root=centroid(1,0);
dfs(root,0);
for(int i=1;i<=n;i++)pt[i]=i;
for(int k=1;k<=n/2;k++){
for(int i=1;i<=n;i++){
while(sz[pt[i]]<k){
used[pt[i]]=true;
pt[i]=parent[pt[i]];
}
}
ans[2*k]=diameter();
}
for(int i=1;i<=n;i++){
if(i%2==1)cout<<"1\n";
else cout<<ans[i]<<"\n";
}
return 0;
}
Compilation message (stderr)
meetings2.cpp: In function 'void dfs(int, int)':
meetings2.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
meetings2.cpp: In function 'int centroid(int, int)':
meetings2.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
meetings2.cpp: In function 'void dfs1(int, int, int)':
meetings2.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |