//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
if(b==0)return 1;
if(b==1)return(a%mod);
int tem=po(a,b/2);
if(b&1)return(((tem*tem)%mod)*a)%mod;
else return(tem*tem)%mod;
}
int GCD(int a,int b){
int x=0;
int ra,rb;
while(a&&b){
if(((a&1)==0)&&((b&1)==0)){
a>>=1,b>>=1,x++;
}
else if((a^b)&1){
if(a&1)b>>=1;
else a>>=1;
}
else{
ra=abs(a-b),rb=min(a,b);
a=ra,b=rb;
}
}
return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int n,cn,mn=1e9,si[200010],pa[200010][18],o[200010],dep[200010];
vector<int> g[200010];
vector<pii> v;
void dfs(int p,int f){
si[p]=1;
int mxs=0;
for(int u:g[p]){
if(u==f)continue;
dfs(u,p);
si[p]+=si[u];
mxs=max(mxs,si[u]);
}
mxs=max(mxs,n-1-mxs);
if(mxs<=mn)mn=mxs,cn=p;
}
void dfs1(int p,int f,int d){
si[p]=1;
pa[p][0]=f;
dep[p]=d;
for(int u:g[p]){
if(u==f)continue;
dfs1(u,p,d+1);
si[p]+=si[u];
}
}
int dis(int x,int y){
if(x==y)return 0;
if(dep[x]<dep[y])swap(x,y);
int len=dep[x]-dep[y];
for(int i=17;i>=0;i--)if(len&(1ll<<i))x=pa[x][i];
if(x==y)return len;
for(int i=17;i>=0;i--){
if(pa[x][i]!=-1&&pa[x][i]!=pa[y][i])len+=(1ll<<(i+1)),x=pa[x][i],y=pa[y][i];
}
return len+2;
}
signed main(){
IOS();
cin>>n;
F(n-1){
int x,y;
cin>>x>>y;
--x,--y;
g[x].pb(y);
g[y].pb(x);
}
if(n==1){
cout<<"1"<<endl;
return 0;
}
dfs(0,-1);
dfs1(cn,-1,0);
Fi(j,17)F(n)pa[i][j+1]=(pa[i][j]==-1?-1:pa[pa[i][j]][j]);
F(n){
if(i!=cn)v.pb({si[i],i});
}
sort(all(v));
pii dip={cn,cn};
int di=0;
for(int i=n-1;i>=0;i--){
if(i%2==0){
o[i]=1;
continue;
}
int k=(i+1)/2;
while(sz(v)&&v.back().X>=k){
int t1,t2;
t1=dis(v.back().Y,dip.X);
t2=dis(v.back().Y,dip.Y);
if(t1>t2){
if(t1>di)dip={v.back().Y,dip.X},di=t1;
}
else{
if(t2>di)dip={v.back().Y,dip.Y},di=t2;
}
v.pop_back();
}
o[i]=di+1;
}
F(n)cout<<o[i]<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5020 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5020 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5020 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5036 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
