#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int INF = 1e9+7;
int N;
vector<int> adj[MAXN+10], VV[MAXN+10];
int sz[MAXN+10], dep[MAXN+10], par[MAXN+10];
int ans[MAXN+10];
vector<int> dfn;
void dfs(int now, int bef, int d)
{
sz[now]=1;
dep[now]=d;
par[now]=bef;
VV[now].push_back(dfn.size());
dfn.push_back(now);
for(int nxt : adj[now])
{
if(nxt==bef) continue;
dfs(nxt, now, d+1);
VV[now].push_back(dfn.size());
dfn.push_back(now);
sz[now]+=sz[nxt];
}
}
struct UF
{
int par[MAXN+10], minv[MAXN+10], maxv[MAXN+10];
void init()
{
for(int i=1; i<=N; i++)
{
par[i]=i;
maxv[i]=minv[i]=dep[i];
}
}
int Find(int x)
{
if(x==par[x]) return x;
return par[x]=Find(par[x]);
}
void Union(int x, int y)
{
x=Find(x); y=Find(y);
minv[x]=min(minv[x], minv[y]);
maxv[x]=max(maxv[x], maxv[y]);
par[y]=x;
}
}uf;
struct Node
{
int a, ab, aba, b, ba;
Node() : a(-INF), ab(-INF), aba(-INF), b(-INF), ba(-INF) {}
};
Node operator + (const Node &p, const Node &q)
{
Node ret;
ret.a=max(p.a, q.a);
ret.b=max(p.b, q.b);
ret.ab=max({p.ab, q.ab, p.a+q.b});
ret.ba=max({p.ba, q.ba, p.b+q.a});
ret.aba=max({p.aba, q.aba, p.a+q.ba, p.ab+q.a});
return ret;
}
struct SEG
{
Node tree[MAXN*8+10];
void update(int node, int tl, int tr, int p, int q)
{
if(tl==tr)
{
if(q==1) tree[node].a=dep[dfn[tl]];
else if(q==2) tree[node].a=-INF;
else tree[node].b=-2*dep[dfn[tl]];
return;
}
int mid=tl+tr>>1;
if(p<=mid) update(node*2, tl, mid, p, q);
else update(node*2+1, mid+1, tr, p, q);
tree[node]=tree[node*2]+tree[node*2+1];
}
int val() { return tree[1].aba; }
}seg;
int main()
{
scanf("%d", &N);
for(int i=1; i<N; i++)
{
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1, 1);
vector<pii> V;
for(int i=2; i<=N; i++)
{
int p=sz[i], q=sz[par[i]];
V.push_back({min({p, N-p, q, N-q}), i});
}
sort(V.begin(), V.end(), greater<pii>());
uf.init();
int val=1;
for(int i=1; i<=N; i++) if(N/2<=sz[i] && sz[i]<=N-N/2) val=2;
for(int i=N/2, j=0; i>=1; i--)
{
for(; j<V.size() && V[j].first>=i; j++)
{
int u=V[j].second;
uf.Union(u, par[u]);
u=uf.Find(u);
val=max(val, uf.maxv[u]-uf.minv[u]+2);
}
ans[i]=val;
}
V.clear();
for(int i=1; i<=N; i++) V.push_back({sz[i], i});
sort(V.begin(), V.end(), greater<pii>());
for(int i=N/2, j=0; i>=1; i--)
{
for(; j<V.size() && V[j].first>=i; j++)
{
if(V[j].second!=1) seg.update(1, 0, dfn.size()-1, VV[par[V[j].second]].front(), 2);
for(auto it : VV[V[j].second]) seg.update(1, 0, dfn.size()-1, it, 0);
seg.update(1, 0, dfn.size()-1, VV[V[j].second].front(), 1);
}
ans[i]=max(ans[i], seg.val()+1);
//printf("!%d\n", seg.val());
}
for(int i=1; i<=N; i++)
{
if(i%2) printf("1\n");
else printf("%d\n", ans[i/2]);
}
}
Compilation message
meetings2.cpp: In member function 'void SEG::update(int, int, int, int, int)':
meetings2.cpp:90:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
90 | int mid=tl+tr>>1;
| ~~^~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:126:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for(; j<V.size() && V[j].first>=i; j++)
| ~^~~~~~~~~
meetings2.cpp:142:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(; j<V.size() && V[j].first>=i; j++)
| ~^~~~~~~~~
meetings2.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
meetings2.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
41044 KB |
Output is correct |
| 2 |
Correct |
23 ms |
40992 KB |
Output is correct |
| 3 |
Correct |
22 ms |
41020 KB |
Output is correct |
| 4 |
Correct |
22 ms |
40948 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
41044 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
41044 KB |
Output is correct |
| 2 |
Correct |
23 ms |
40992 KB |
Output is correct |
| 3 |
Correct |
22 ms |
41020 KB |
Output is correct |
| 4 |
Correct |
22 ms |
40948 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
41044 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
41044 KB |
Output is correct |
| 2 |
Correct |
23 ms |
40992 KB |
Output is correct |
| 3 |
Correct |
22 ms |
41020 KB |
Output is correct |
| 4 |
Correct |
22 ms |
40948 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
41044 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
