#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const int inf = 1e9;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 2e5+5;
vector<int> g[maxn];
int sz[maxn], L[maxn], R[maxn], par[maxn], dep[maxn];
vector<int> children[maxn]; // including self
int IT = 0;
int lca[4005][4005];
void dfsqua(int v, int p) {
par[v] = p;
sz[v] = 1;
L[v] = R[v] = IT++;
children[v].pb(v);
for (int u : g[v]) {
if (u != p) {
dep[u] = dep[v] + 1;
dfsqua(u,v);
sz[v] += sz[u];
R[v] = R[u];
for (int c : children[u]) {
children[v].pb(c);
}
}
}
}
void dfs(int v, int p) {
par[v] = p;
sz[v] = 1;
L[v] = R[v] = IT++;
for (int u : g[v]) {
if (u != p) {
dep[u] = dep[v] + 1;
dfs(u,v);
sz[v] += sz[u];
R[v] = R[u];
}
}
}
vector<int> ord;
bool alive[maxn];
struct S{
int a, b, ab, bc, abc;
}s[400005 * 4];
S pull(S x, S y){
S r;
r.a=max(x.a, y.a);
r.b=max(x.b, y.b);
r.ab=max(x.ab,y.ab);
r.bc=max(x.bc,y.bc);
r.abc=max(x.abc,y.abc);
MX(r.ab, x.a+y.b);
MX(r.bc, x.b+y.a);
MX(r.abc, x.ab+y.a);
MX(r.abc, x.a+y.bc);
return r;
}
void MO(int p, bool on, int o=1, int l=0, int r=SZ(ord)-1) {
if (l > p || r < p) return;
if (l == r) {
int a = ord[l];
if (on) {
s[o] = {
dep[a],
dep[a]*-2,
-dep[a],
-dep[a],
0
};
}else{
s[o] = {
-inf,
dep[a]*-2,
-inf,
-inf,
-inf
};
}
return;
}
int mid = l+r>>1;
MO(p,on, o*2,l,mid);
MO(p,on, o*2+1,mid+1,r);
s[o] = pull(s[o*2], s[o*2+1]);
}
void dfs2(int v, int p) {
L[v] = R[v] = SZ(ord);
ord.pb(v);
par[v] = p;
sz[v] = 1;
for (int u : g[v]) {
if (u != p) {
dep[u] = dep[v] + 1;
dfs2(u,v);
R[v] = SZ(ord);
ord.pb(v);
sz[v] += sz[u];
}
}
}
bool isAnc(int a, int b) {
// is a b's ancestor?
return L[a] <= L[b] && R[a] >= R[b];
}
int n;
vector<int> quadratic() {
dfsqua(0, -1);
REP(i,n) {
for (int c : children[i]) {
lca[i][c] = lca[c][i] = i;
}
for (int c : g[i]) {
if (c != par[i]) {
for (int c2 : g[i]) {
if (c2 > c && c2 != par[i]) {
for (int v1 : children[c]) for (int v2 : children[c2]) {
lca[v1][v2] = lca[v2][v1] = i;
}
}
}
}
}
}
vector<int> dst(n); // max accommodation for this length
auto go = [&](int a, int b, int s1, int s2) {
bug(a,b,s1,s2);
bug(dep[a] + dep[b] - dep[lca[a][b]]*2);
MX(dst[dep[a] + dep[b] - dep[lca[a][b]]*2], min(s1, s2) * 2);
};
REP(a,n) for (int j : g[a]) if (j != par[a]) {
for (int b : children[j]) {
go(a,b,n-sz[j],sz[b]);
}
}
REP(i,n) REP(j,i) {
int a = i, b = j;
if (dep[a] > dep[b]) swap(a,b);
int s1, s2;
if (isAnc(a,b)) {
continue;
}
s1 = sz[a];
s2 = sz[b];
go(a,b,s1,s2);
// bug(a,b,lca[a][b], s1, s2);
// bug(dep[a] + dep[b] - dep[lca[a][b]] * 2);
}
for (int i = n-2; i>=0; --i) {
MX(dst[i], dst[i+1]);
}
vector<int> ret(n+1);
int j = 0;
for (int i = n; i>=1; --i) {
if (i % 2 == 1) ret[i] = 1;
else{
while (j+1 < n && dst[j+1] >= i) {
++j;
}
ret[i] = j+1;
bug(i, ret[i]);
}
}
return ret;
}
int cen(int v) {
for (int u : g[v]) {
if (u!=par[v] && sz[u] >= (n+1)/2) {
return cen(u);
}
}
return v;
}
//int csz[maxn]; // centroid based sizes
vector<int> who[maxn];
vector<int> fast(){
dfs(0,-1);
int rt = cen(0), rt2 = -1;
if (sz[rt] == n-sz[rt]) {
rt2 = par[rt];
}
bug(rt, rt2);
dep[rt] = 0;
dfs2(rt, rt); // now everything is relative to the new root
REP(i,n) {
if (i != rt)
who[sz[i]].pb(i);
}
vector<int> ret(n+1);
#ifdef BALBIT
for (int x : ord) cout<<x<<' ';
cout<<endl;
#endif
REP(i,n) {
MO(L[i], 1);
}
for (int i = 1; i<=n; ++i ) {
if (i & 1) {
ret[i] = 1;
}else{
bug(i, s[1].abc+1);
ret[i] = s[1].abc+1;
for (int x : who[i/2]) {
MO(L[x], 0);
}
}
}
for (int t : g[rt]) {
bug(t, sz[t]);
MX(ret[sz[t] * 2], 2);
}
return ret;
}
signed main(){
IOS();
cin>>n;
REP(i,n-1) {
int a,b; cin>>a>>b; --a; --b;
g[a].pb(b); g[b].pb(a);
}
vector<int> yay = fast();
REP1(i,n) {
cout<<yay[i]<<endl;
}
}
Compilation message
meetings2.cpp: In function 'void MO(int, bool, int, int, int)':
meetings2.cpp:138:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
138 | int mid = l+r>>1;
| ~^~
meetings2.cpp: In function 'std::vector<int> fast()':
meetings2.cpp:250:22: warning: variable 'rt2' set but not used [-Wunused-but-set-variable]
250 | int rt = cen(0), rt2 = -1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14444 KB |
Output is correct |
| 3 |
Correct |
9 ms |
14360 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14444 KB |
Output is correct |
| 3 |
Correct |
9 ms |
14360 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14444 KB |
Output is correct |
| 3 |
Correct |
9 ms |
14360 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
