#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/
using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;
// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
//***************** CONSTANTS *****************
const int MXN = 200000;
const int K = 20;
//***************** GLOBAL VARIABLES *****************
vector<int> g[MXN];
int up[K][MXN], sub[MXN], tin[MXN], tout[MXN], timer, depth[MXN], ans[MXN + 1], counter[MXN];
bool added[MXN];
//***************** AUXILIARY STRUCTS *****************
void dfs(int p, int u){
depth[u] = depth[p] + 1;
tin[u] = timer++;
up[0][u] = p;
for(int i = 1; i < K; i++)
up[i][u] = up[i-1][up[i-1][u]];
for(int v : g[u]) if(v != p){
dfs(u, v);
}
tout[u] = timer;
}
bool check(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(check(u, v)) return u;
if(check(v, u)) return v;
for(int i = K - 1; i >= 0; --i){
if(!check(up[i][u], v))
u = up[i][u];
}
return up[0][u];
}
int dist(int u, int v){
return depth[u] + depth[v] - 2*depth[lca(u, v)];
}
//***************** MAIN BODY *****************
void solve(){
int N;
cin >> N;
for(int i = 0; i < N - 1; i++){
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(0, 0);
vector<int> leaf[N+1];
for(int i = 0; i < N; i++)
if(g[i].size() == 1){
leaf[1].push_back(i);
added[i] = 1;
}
fill(sub, sub + N, 1);
for(int s = 1; s <= N; s++) for(int x : leaf[s]) for(int v : g[x]){
if(added[v]) continue;
counter[v]++;
sub[v] += sub[x];
if(counter[v] == g[v].size() - 1){
added[v] = 1;
leaf[sub[v]].push_back(v);
}
}
array<int, 2> e = {-1, -1};
int j = N >> 1;
for(int s = N; s >= 1; --s) for(int x : leaf[s]){
if(e[0] == -1)
e[0] = x;
else if(e[1] == -1)
e[1] = x;
else{
// array<int, 2> temp[2] = {{e[0], x}, {x, e[1]}};
// for(auto& [u, v] : temp)
// if(dist(e[0], e[1]) < dist(u, v))
// e = {u, v};
if(dist(e[0], x) > dist(e[0], e[1])) e[1] = x;
else if(dist(e[1], x) > dist(e[0], e[1])) e[0] = x;
}
if(e[1] == -1) continue;
while(j > min(sub[e[0]], sub[e[1]]))
--j;
ans[2*j] = dist(e[0], e[1]) + 1;
}
for(int i = (N >> 1) - 1; i >= 1; --i)
ans[i<<1] = max(ans[i<<1], ans[2 + i<<1]);
for(int i = 1; i <= N; i++)
if(i & 1) cout << 1 << '\n';
else cout << ans[i] << '\n';
}
//***************** *****************
int32_t main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
#ifdef LOCAL
auto begin = high_resolution_clock::now();
#endif
int tc = 1;
// cin >> tc;
for (int t = 0; t < tc; t++)
solve();
#ifdef LOCAL
auto end = high_resolution_clock::now();
cout << fixed << setprecision(4);
cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
#endif
return 0;
}
/*
If code gives a WA, check for the following :
1. I/O format
2. Are you clearing all global variables in between tests if multitests are a thing
3. Can you definitively prove the logic
4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity,
use faster io
*/
Compilation message
meetings2.cpp: In function 'void solve()':
meetings2.cpp:94:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | if(counter[v] == g[v].size() - 1){
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
meetings2.cpp:128:36: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
128 | ans[i<<1] = max(ans[i<<1], ans[2 + i<<1]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
