/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) ((ll)x.size())
#define all(x) (x).begin(),(x).end()
#define kill(x) cout << x << '\n', exit(0);
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define endl '\n'
const int N = 3e5+23, lg = 18;
ll Mod = 1e9+7; //998244353;
inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
ll ans = 1;
a=MOD(a, mod);
while (b) {
if (b & 1) ans = MOD(ans*a, mod);
b >>= 1;
a = MOD(a*a, mod);
}
return ans;
}
int n, h[N], subt[N], ans[N], seg[5][2*N], par[lg][N];
vector<int> adj[N];
void update(int ind, int val, int id) {
if(ind == 0) return;
if(ind >= (1<<lg)) {
if(val==-1) seg[id][ind] = 0;
seg[id][ind] = max(seg[id][ind], val);
} else {
seg[id][ind] = max(seg[id][2*ind], seg[id][2*ind+1]);
}
update(ind/2, val, id);
}
int query(int l, int r, int id, int ind=1, int lc=1, int rc=(1<<lg)+1) {
if(lc>=r || l>=rc) return -n;
if(lc>=l && rc<=r) return seg[id][ind];
int mid = (lc+rc)/2;
int res = max(query(l, r, id, 2*ind, lc, mid), query(l, r, id, 2*ind+1, mid, rc));
if(res == 0) return -n;
return res;
}
void init(int v, int p=0) {
subt[v] = 1, h[v] = h[p] + 1, par[0][v] = p;
for(int i=1; i<lg; i++) par[i][v] = par[i-1][par[i-1][v]];
for(int u : adj[v]) {
if(u == p) continue;
init(u, v); subt[v] += subt[u];
}
}
void add(int v, int p, int id) {
update(subt[v]+(1<<lg)-1, h[v], id);
for(int u : adj[v]) {
if(u == p) continue;
add(u, v, id);
}
}
void clen(int v, int p, int id) {
update(subt[v]+(1<<lg)-1, -1, id);
for(int u : adj[v]) {
if(u == p) continue;
clen(u, v, id);
}
}
void dfs(int v, int p=0) {
int mx = 0;
for(int u : adj[v]) {
if(u == p) continue;
mx = (subt[mx] > subt[u] ? mx : u);
}
if(mx == 0) {
ans[2] = max(ans[2], 2);
update((1<<lg)+subt[v]-1, h[v], 1);
return;
}
for(int u : adj[v]) {
if(u == p || u == mx) continue;
dfs(u, v);
clen(u, v, 1);
}
for(int u : adj[v]) {
if(u == p || u == mx) continue;
add(u, v, 3);
for(int i=1; i<=subt[u]; i++) {
ans[2*i] = max(ans[2*i], query(i, n+1, 3)+query(i, n+1, 2)+1-2*h[v]);
}
clen(u, v, 3);
add(u, v, 2);
}
for(int u : adj[v]) {
if(u == p || u == mx) continue;
clen(u, v, 2);
}
reverse(all(adj[v]));
for(int u : adj[v]) {
if(u == p || u == mx) continue;
add(u, v, 3);
int x = n-subt[u];
ans[2*x] = max(ans[2*x], query(x, n+1, 3)-h[v]+1);
for(int i=1; i<=subt[u]; i++) {
ans[2*i] = max(ans[2*i], query(i, n+1, 3)+query(i, n+1, 2)+1-2*h[v]);
}
clen(u, v, 3);
add(u, v, 2);
}
reverse(all(adj[v]));
if(mx > 0) dfs(mx, v);
for(int i=1; i<=subt[v]-subt[mx]; i++) {
ans[2*i] = max(ans[2*i], query(i, n+1, 1)+query(i, n+1, 2)+1-2*h[v]);
}
int x = n-subt[mx];
ans[2*x] = max(ans[2*x], query(x, n+1, 1)-h[v]+1);
int w = v;
for(int i=lg-1; i>=0; i--) {
if(par[i][w]<=1) continue;
int ff = par[i][w];
if(subt[par[0][ff]] - subt[ff] >= subt[v]) {
w = ff;
}
}
if(subt[par[0][w]] - subt[w] >= subt[v]) {
ans[2*subt[v]] = max(ans[2*subt[v]], h[v]-h[w]+2);
}
// add to seg1
for(int u : adj[v]) {
if(u == p || u == mx) continue;
add(u, v, 1);
clen(u, v, 2);
}
update(subt[v]+(1<<lg)-1, h[v], 1);
}
int main () {
ios_base::sync_with_stdio(false), cin.tie(0);
cin>>n;
for(int v,u,i=1; i<n; i++) {
cin>>v>>u; adj[v].pb(u); adj[u].pb(v);
}
init(1);
dfs(1);
for(int i=n; i>=1; i--) {
ans[i] = max(ans[i+1], ans[i]);
}
for(int i=1; i<=n; i++) {
if(i%2 == 1) cout<<1<<endl;
else cout<<max(1, ans[i])<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33372 KB |
Output is correct |
| 2 |
Correct |
6 ms |
33372 KB |
Output is correct |
| 3 |
Correct |
6 ms |
33372 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
33372 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33372 KB |
Output is correct |
| 2 |
Correct |
6 ms |
33372 KB |
Output is correct |
| 3 |
Correct |
6 ms |
33372 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
33372 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33372 KB |
Output is correct |
| 2 |
Correct |
6 ms |
33372 KB |
Output is correct |
| 3 |
Correct |
6 ms |
33372 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
33372 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
