#include <bits/stdc++.h>
using namespace std;
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
*/
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
ll MOD = 1000000007;
ll MOD1 = 998244353;
ll power(ll base, ll n){
if (n == 0) return 1;
if (n == 1) return base;
ll halfn = power(base, n/2);
if (n % 2 == 0) return (halfn * halfn) % MOD;
return (((halfn * halfn) % MOD) * base) % MOD;
}
ll inverse(ll n){
return power(n, MOD-2);
}
ll add(ll a, ll b){
return (a+b) % MOD;
}
ll mul(ll a, ll b){
a %= MOD;
return (a*b) % MOD;
}
ll gcd(ll a, ll b){
if (a == 1) return 1;
if (a == 0) return b;
return gcd(b%a, a);
}
ld pi = 3.141592653589793238;
struct segtree{
vector<ll> op, ans;
int sz = 0;
void init(int n){
sz = n;
op.assign(4*n, -1);
ans.assign(4*n, 0);
}
void prop(int v, int tl, int tr){
if (op[v] == -1 || tl == tr) return;
int tm = (tl+tr)/2;
op[2*v] = op[v];
op[2*v+1] = op[v];
ll len1 = tm-tl+1, len2 = tr-tm;
ans[2*v] = op[v] * len1;
ans[2*v+1] = op[v] * len2;
op[v] = -1;
}
void update(int v, int tl, int tr, int l, int r, int val){
prop(v, tl, tr);
if (l > r) return;
if (tl == l && tr == r){
op[v] = val;
ll len = tr-tl+1;
ans[v] = val * len;
return;
}
int tm = (tl+tr)/2;
update(2*v, tl, tm, l, min(r,tm), val);
update(2*v+1, tm+1, tr, max(l, tm+1), r, val);
ans[v] = ans[2*v] + ans[2*v+1];
}
void update(int l, int r, int val){
update(1, 0, sz-1, l, r, val);
}
ll get(int v, int tl, int tr, int l, int r){
prop(v, tl, tr);
if (l > r) return 0;
if (tl == l && tr == r) return ans[v];
int tm = (tl+tr)/2;
ll m1 = get(2*v, tl, tm, l, min(r, tm));
ll m2 = get(2*v+1, tm+1, tr, max(l, tm+1), r);
return m1 + m2;
}
ll get(int l, int r){
return get(1, 0, sz-1, l, r);
}
};
const int N = 200001;
vi g[N], sz(N), ans(N), dist(N);
void dfs1(int u, int p){
sz[u] = 1;
for (int v : g[u]){
if (v==p) continue;
dist[v] = dist[u]+1;
dfs1(v,u);
sz[u]+=sz[v];
}
}
void dfs2(int u, int p, int cur){
int val = min(cur, sz[u]);
ans[val*2] = max(ans[val*2], dist[u]+1);
for (int v : g[u]){
if (v==p) continue;
dfs2(v,u,cur);
}
}
void solve(){
int n; cin >> n;
FOR(i,0,n-1){
int u, v; cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
FOR(i,1,n+1){
dfs1(i,0);
for (int u : g[i]){
dfs2(u,i,n-sz[u]);
}
FOR(j,1,n+1) dist[j] = 0;
}
ROF(i,n/2-1,1){
ans[i*2] = max(ans[i*2], ans[(i+1)*2]);
}
FOR(i,1,n+1){
if (i % 2 == 1) cout << 1 << '\n';
else cout << ans[i] << '\n';
}
}
int main(){
cout << fixed << setprecision(8);
ios::sync_with_stdio(false);
if (fopen("input.txt", "r")) {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
int TC = 1;
//cin >> TC;
FOR(i, 1, TC+1){
//cout << "Case #" << i << ": ";
solve();
}
}
Compilation message
meetings2.cpp: In function 'int main()':
meetings2.cpp:152:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:153:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7396 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7396 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7396 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
