#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=2e5, INF=1e9;
int n, d[mxN], s[mxN], anc[mxN][18], ans[mxN+1], tin[mxN], tout[mxN];
vector<int> adj[mxN], stk;
set<ar<int, 2>> active, highest;
void dfs(int u=0) {
s[u]=1;
tin[u]=stk.size();
stk.push_back(d[u]);
for (int i=1; i<18; ++i)
anc[u][i]=anc[anc[u][i-1]][i-1];
for (int v : adj[u])
if (v!=anc[u][0]) {
d[v]=d[u]+1, anc[v][0]=u;
dfs(v);
s[u]+=s[v];
stk.push_back(d[u]);
}
tout[u]=stk.size()-1;
}
bool ia(int u, int v) {
return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
int lca(int u, int v) {
if (ia(u, v)||ia(v, u))
return ia(u, v)?u:v;
for (int i=17; ~i; --i)
if (!ia(anc[u][i], v))
u=anc[u][i];
return anc[u][0];
}
int dist(int u, int v) {
return d[u]+d[v]-2*d[lca(u, v)];
}
struct Node {
int ans, mn, mx, lhs, rhs;
} st[1<<20];
Node cmb(Node a, Node b) {
return {
max({a.ans, b.ans, a.rhs+b.mx, a.mx+b.lhs}),
min(a.mn, b.mn),
max(a.mx, b.mx),
max({a.lhs, b.lhs, -2*a.mn+b.mx}),
max({a.rhs, b.rhs, a.mx-2*b.mn})
};
}
void bld(int u=1, int l=0, int r=2*n-2) {
if (l==r) {
st[u].mn=stk[l];
st[u].mx=st[u].lhs=st[u].rhs=-INF;
return;
}
int mid=(l+r)/2;
bld(2*u, l, mid);
bld(2*u+1, mid+1, r);
st[u]=cmb(st[2*u], st[2*u+1]);
}
void upd(int i, bool on, int u=1, int l=0, int r=2*n-2) {
if (l==r) {
//cout << "activating " << i << " " << on << endl;
st[u].mx=on?stk[l]:-INF;
st[u].lhs=st[u].rhs=on?-stk[l]:-INF;
return;
}
int mid=(l+r)/2;
i<=mid?upd(i, on, 2*u, l, mid):upd(i, on, 2*u+1, mid+1, r);
st[u]=cmb(st[2*u], st[2*u+1]);
}
int before(set<ar<int, 2>>& nodes, int u) {
auto it=nodes.lower_bound({tin[u]});
if (it!=nodes.begin()) {
int v=(*prev(it))[1];
return ia(v, u)?v:-1;
}
return -1;
}
struct Boring_Old_Range_Max_Segment_Tree_Ugh {
int st[1<<20];
void upd(int i, int x, int u=1, int l=0, int r=2*n-2) {
if (l==r) { st[u]=x; return; }
int mid=(l+r)/2;
i<=mid?upd(i, x, 2*u, l, mid):upd(i, x, 2*u+1, mid+1, r);
st[u]=max(st[2*u], st[2*u+1]);
}
int qry(int ql, int qr, int u=1, int l=0, int r=2*n-2) {
if (l>qr||r<ql) return 0;
if (ql<=l&&r<=qr) return st[u];
int mid=(l+r)/2;
return max(qry(ql, qr, 2*u, l, mid), qry(ql, qr, 2*u+1, mid+1, r));
}
} st_max;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i=1; i<n; ++i) {
int u, v;
cin >> u >> v, --u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs();
assert(stk.size()==2*n-1);
bld();
vector<ar<int, 2>> subtrees, uptrees;
for (int i=1; i<n; ++i) {
subtrees.push_back({s[i], i});
uptrees.push_back({n-s[i], i});
}
sort(subtrees.begin(), subtrees.end());
sort(uptrees.begin(), uptrees.end());
memset(st_max.st, -1, sizeof(st_max.st));
fill(ans, ans+n+1, 1);
int best=1;
for (int i=n/2; i; --i) {
while(subtrees.size()&&subtrees.back()[0]>=i) {
int u=subtrees.back()[1];
subtrees.pop_back();
auto it=active.lower_bound({tin[u]});
int v=before(active, u);
if (v!=-1) {
upd(tin[v], 0);
active.erase({tin[v], v});
}
upd(tin[u], 1);
active.insert({tin[u], u});
st_max.upd(tin[u], d[u]);
v=before(highest, u);
if (v!=-1)
best=max(best, d[u]-d[v]+2);
}
best=max(best, st[1].ans+1);
while(uptrees.size()&&uptrees.back()[0]>=i) {
int u=uptrees.back()[1];
uptrees.pop_back();
auto it=highest.lower_bound({tin[u]});
bool fine=1;
if (it!=highest.begin()) {
--it;
int v=(*it)[1];
fine=!ia(v, u);
}
if (fine) {
for (it=highest.lower_bound({tin[u]}); it!=highest.end()&&ia(u, (*it)[1]); it=highest.erase(it));
highest.insert({tin[u], u});
best=max(best, st_max.qry(tin[u], tout[u])-d[u]+2);
}
}
ans[2*i]=best;
}
for (int i=1; i<=n; ++i)
cout << ans[i] << "\n";
return 0;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from meetings2.cpp:1:
meetings2.cpp: In function 'int main()':
meetings2.cpp:119:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
119 | assert(stk.size()==2*n-1);
| ~~~~~~~~~~^~~~~~~
meetings2.cpp:137:9: warning: variable 'it' set but not used [-Wunused-but-set-variable]
137 | auto it=active.lower_bound({tin[u]});
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9044 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9044 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9044 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9044 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
9044 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9044 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9044 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9044 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9044 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
9044 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
9044 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9044 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9044 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9044 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
9044 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
