#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000010
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define fmax(x, a) (x) = (max((x), (a)))
int N;
vector<int> adj[MAX];
int num[MAX];
int popv[MAX];
set<pii> st[MAX];
int dep[MAX];
int ans[MAX];
void dfs(int x, int p = 0, int d = 1) {
num[x] = 1, dep[x] = d;
for (auto v : adj[x]) if (v != p) dfs(v, x, d + 1), num[x] += num[v];
}
void add(int sub, int d, int x) {
auto it = st[x].lower_bound(pii(sub, 0));
if (it != st[x].end() && it->second > d) return;
while (1) {
auto it = st[x].lower_bound(pii(sub + 1, 0));
if (it == st[x].begin()) break;
it--;
if (it->second <= d) st[x].erase(it);
else break;
}
st[x].emplace(sub, d);
}
void calc(int x, int p = 0) {
for (auto v : adj[x]) {
if (v == p) continue;
calc(v, x);
int upst = N - num[v];
fmax(ans[upst], popv[v] - dep[x]);
while (st[v].size() && st[v].rbegin()->first >= upst) {
fmax(ans[upst], st[v].rbegin()->second - dep[x]);
fmax(ans[st[v].rbegin()->first], st[v].rbegin()->second - dep[x] - 1);
fmax(popv[x], st[v].rbegin()->second);
st[v].erase(*st[v].rbegin());
}
if (st[x].size() < st[v].size()) swap(st[v], st[x]);
for (auto& [subt, d] : st[v]) {
auto it = st[x].lower_bound(pii(subt, 0));
if (it != st[x].end()) fmax(ans[subt], d + it->second - dep[x] * 2);
if (it != st[x].begin()) --it, fmax(ans[min(subt, it->first)], d + it->second - dep[x] * 2);
}
for (auto& [subt, d] : st[v]) add(subt, d, x);
}
add(num[x], dep[x], x);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N;
int i, a, b;
for (i = 1; i < N; i++) cin >> a >> b, adj[a].push_back(b), adj[b].push_back(a);
dfs(1);
calc(1);
for (i = N; i >= 1; i--) fmax(ans[i], ans[i + 1]);
for (i = 1; i <= N; i++) {
if (i & 1) cout << 1 << ln;
else cout << ans[i >> 1] + 1 << ln;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14500 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14500 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14500 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
