// #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];
void update(int i, int l, int r, int p, int v) {
if(p > r or l > p) return;
if(l == r) {
mx[i] = max(mx[i], v);
}
else {
int mi = l + r >> 1;
update(i << 1, l, mi, p, v);
update(i << 1 | 1, mi + 1, r, p, v);
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
}
}
int get(int i, int l, int r, int ll, int rr) {
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));
}
int mx2[maxn << 2];
void update2(int i, int l, int r, int ll, int rr, int v) {
if(ll > r or l > rr) return;
if(ll <= l and r <= rr) {
mx2[i] = max(mx2[i], v);
}
else {
int mi = l + r >> 1;
update2(i << 1, l, mi, ll, rr, v);
update2(i << 1 | 1, mi + 1, r, ll, rr, v);
}
}
int get2(int i, int l, int r, int p) {
if(p > r or l > p) return -inf;
int re = -inf;
if(l <= p and p <= r) {
re = mx2[i];
}
if(l < r) {
int mi = l + r >> 1;
re = max({re, get2(i << 1, l,mi, p), get2(i << 1 | 1, mi + 1, r, p)});
}
return re;
}
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;
}
ii dp[maxn][2];
void prep(int i, int p) {
sz[i] = 1;
dep[i] = i == p? 0: 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 mydep = dep[i]; // one is ancestor of another
int mx = mydep;
while(1) {
// prep for on off
update2(1, 1, n, in[head[i]], in[i] - 1, mydep); // max that comes from heavy child
// off on
mx = max(mx, get(1,1, n, in[head[i]], in[i] - 1) + mydep);
// JUMP
if(head[i] == par[head[i]]) return mx;
int temp = head[i];
i = par[head[i]];
// off, off
if(dp[i][0].se == temp) dp[i][0] = {mydep, temp};
else if(dp[i][1].se == temp) dp[i][1] = {mydep, temp};
else if(dp[i][1].fi < mydep) dp[i][1] = {mydep, temp};
if(dp[i][0] < dp[i][1]) swap(dp[i][0], dp[i][1]);
mx = max(mx, dp[i][0].fi + dp[i][1].fi - 2 * dep[i]);
// on off
mx = max(mx, mydep + get2(1, 1, n, in[i]) - 2 * dep[i]);
// prep for off on
update(1, 1, n, in[i], mydep - 2 * dep[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;
fill(all(mx), -inf);
fill(all(mx2), -inf);
fori(i,1,n) dp[i][0] = dp[i][1] = ii(-inf, -inf);
fori(i,1,n) {
ev[sz[i]].eb(i);
}
ford(i, n, 1) {
if(i & 1) {
}
else {
ans[i] = ans[i + 2];
for(auto id: ev[i / 2]) {
// cout << id << sp << climb(id) << sp << climb(id) + dep[id] << endl;
ans[i] = max(ans[i], climb(id));
}
}
}
fori(i,1,n) {
cout << ans[i] + 1 << endl;
}
}
Compilation message
meetings2.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:85:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | 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:95:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int mi = l + r >> 1;
| ~~^~~
meetings2.cpp: In function 'void update2(long long int, long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:107:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
107 | int mi = l + r >> 1;
| ~~^~~
meetings2.cpp: In function 'long long int get2(long long int, long long int, long long int, long long int)':
meetings2.cpp:120:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
120 | int mi = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
22192 KB |
Output is correct |
| 2 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 3 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 4 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 5 |
Correct |
11 ms |
22232 KB |
Output is correct |
| 6 |
Correct |
11 ms |
22276 KB |
Output is correct |
| 7 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 8 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 9 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 10 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 11 |
Correct |
12 ms |
22172 KB |
Output is correct |
| 12 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 13 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 14 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 15 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 16 |
Correct |
11 ms |
22324 KB |
Output is correct |
| 17 |
Correct |
11 ms |
22328 KB |
Output is correct |
| 18 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 19 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 20 |
Correct |
11 ms |
22276 KB |
Output is correct |
| 21 |
Correct |
11 ms |
22220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
22192 KB |
Output is correct |
| 2 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 3 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 4 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 5 |
Correct |
11 ms |
22232 KB |
Output is correct |
| 6 |
Correct |
11 ms |
22276 KB |
Output is correct |
| 7 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 8 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 9 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 10 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 11 |
Correct |
12 ms |
22172 KB |
Output is correct |
| 12 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 13 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 14 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 15 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 16 |
Correct |
11 ms |
22324 KB |
Output is correct |
| 17 |
Correct |
11 ms |
22328 KB |
Output is correct |
| 18 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 19 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 20 |
Correct |
11 ms |
22276 KB |
Output is correct |
| 21 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 22 |
Correct |
21 ms |
22836 KB |
Output is correct |
| 23 |
Incorrect |
19 ms |
22828 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
22192 KB |
Output is correct |
| 2 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 3 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 4 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 5 |
Correct |
11 ms |
22232 KB |
Output is correct |
| 6 |
Correct |
11 ms |
22276 KB |
Output is correct |
| 7 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 8 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 9 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 10 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 11 |
Correct |
12 ms |
22172 KB |
Output is correct |
| 12 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 13 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 14 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 15 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 16 |
Correct |
11 ms |
22324 KB |
Output is correct |
| 17 |
Correct |
11 ms |
22328 KB |
Output is correct |
| 18 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 19 |
Correct |
12 ms |
22220 KB |
Output is correct |
| 20 |
Correct |
11 ms |
22276 KB |
Output is correct |
| 21 |
Correct |
11 ms |
22220 KB |
Output is correct |
| 22 |
Correct |
21 ms |
22836 KB |
Output is correct |
| 23 |
Incorrect |
19 ms |
22828 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
