// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front
#define fr front
#define bc back
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)
#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
void solve();
signed main() {
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
// fastio();
int tc = 1;
fori(test, 1, tc) {
solve();
}
return 0;
}
#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;
const int maxn = 2e5 + 5, inf = LLONG_MAX / 10ll;
int n;
vi g[maxn];
int sz[maxn];
int cen;
int dep[maxn], hv[maxn], head[maxn], par[maxn]; int in[maxn], inptr, id[maxn];
int mx[maxn << 2], base[maxn << 2];
int lz[maxn << 2];
void build(int i, int l, int r) {
if(l == r) {
base[i] = -2 * dep[id[l]];
mx[i] = -inf;
}
else {
int mi = l + r >> 1;
build(i << 1, l, mi);
build(i << 1 | 1, mi + 1, r);
base[i] = max(base[i << 1], base[i << 1 | 1]);
mx[i] = -inf;
}
}
void pd(int i, int l, int r) {
mx[i] = max(mx[i], base[i] + lz[i]);
if(l < r) {
lz[i << 1] = max(lz[i << 1], lz[i]);
lz[i << 1 | 1] = max(lz[i << 1 | 1], lz[i]);
}
}
void update(int i, int l, int r, int ll, int rr, int v) {
pd(i, l, r);
if(ll > r or l > rr) return;
if(ll <= l and r <= rr) {
lz[i] = max(lz[i], v);
pd(i, l, r);
}
else {
int mi = l + r >> 1;
update(i << 1, l, mi, ll, rr, v);
update(i << 1 | 1, mi + 1, r, ll, rr, v);
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
}
}
int get(int i, int l, int r, int ll, int rr) {
pd(i, l, r);
if(ll > r or l > rr) return -inf;
if(ll <= l and r <= rr) return mx[i];
int mi = l + r >> 1;
return max(get(i << 1, l, mi, ll, rr), get(i << 1 | 1, mi + 1, r, ll, rr));
}
void getsz(int i, int p) {
sz[i] = 1;
for(int j: g[i]) {
if(j - p) {
getsz(j, i);
sz[i] += sz[j];
}
}
}
int getcen(int i,int p) {
for(int j: g[i]) {
if(j - p) {
if(sz[j] * 2 > n) return getcen(j, i);
}
}
return i;
}
void prep(int i, int p) {
sz[i] = 1;
dep[i] = dep[p] + 1;
par[i] = p;
for(int j: g[i]) {
if(j - p) {
prep(j, i);
sz[i] += sz[j];
if(!hv[i] or sz[j] > sz[hv[i]]) hv[i] = j;
}
}
}
void hld(int i, int p) {
in[i] = ++inptr; id[inptr] = i; head[i] = (i == hv[p]? head[p]: i);
if(hv[i]) {
hld(hv[i], i);
}
for(int j: g[i]) {
if(j - p and j - hv[i]) {
hld(j, i);
}
}
}
int climb(int i) {
int mx = -inf;
while(1) {
// cout << i << endl;
mx = max(mx, get(1,1, n, in[head[i]], in[i]));
if(head[i] == par[head[i]]) return mx;
assert(i);
i = par[head[i]];
}
}
void updatepath(int i, int v) {
while(1) {
// cout << i << endl;
update(1,1, n, in[head[i]], in[i], v);
if(head[i] == par[head[i]]) return;
i = par[head[i]];
assert(i);
}
}
vi ev[maxn];
int ans[maxn];
void solve() {
cin >> n;
fori(i,1,n - 1) {
int u, v; cin >> u >> v;
g[u].eb(v);
g[v].eb(u);
}
getsz(1,1);
int root = getcen(1,1);
getsz(root, root);
prep(root, root);
hld(root, root);
// fori(i,1,n) cout << id[i] << sp << par[head[id[i]]] << endl;
build(1,1,n);
//
fori(i,1,n) {
ev[sz[i]].eb(i);
}
updatepath(root, dep[root]);
ford(i, n, 1) {
if(i & 1) {
ans[i] = 1;
}
else {
for(auto id: ev[i / 2]) {
ans[i] = max({1ll, ans[i + 2], climb(id) + dep[id] + 1});
updatepath(id, dep[id]);
}
}
}
fori(i,1,n) {
cout << ans[i] << endl;
}
}
Compilation message
meetings2.cpp: In function 'void build(long long int, long long int, long long int)':
meetings2.cpp:87:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int mi = l + r >> 1;
| ~~^~~
meetings2.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:112:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
112 | int mi = l + r >> 1;
| ~~^~~
meetings2.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:123:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
123 | int mi = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9716 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9676 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9676 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9716 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9676 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9676 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9716 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9676 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9676 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
