#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
const int N = 2e5 + 5;
int n;
int sz[N];
int ans[N];
bool blocked[N];
vector<int> g[N];
void find_sizes(int v, int p) {
sz[v] = 1;
for (int u : g[v]) {
if (!blocked[u] && u != p) {
find_sizes(u, v);
sz[v] += sz[u];
}
}
}
int find_centroid(int v, int p, int x) {
for (int u : g[v]) {
if (!blocked[u] && u != p && sz[u] > x / 2) {
return find_centroid(u, v, x);
}
}
return v;
}
void dfs(int v, int p, int dep, vector<pair<int, int>>& vec) {
vec.emplace_back(sz[v], dep);
for (int u : g[v]) {
if (!blocked[u] && u != p) {
dfs(u, v, dep + 1, vec);
}
}
}
void merge(set<pair<int, int>>& se, vector<pair<int, int>>& vec) {
for (auto [sub, dep] : vec) {
auto it = se.lower_bound(make_pair(sub, -1));
if (it == se.end()) {
se.emplace(sub, dep);
} else {
if (it->second >= dep) {
continue;
}
it = se.insert({sub, dep}).first;
vector<pair<int, int>> to_erase;
while (it != se.begin()) {
it = prev(it);
if (it->second < dep) {
to_erase.push_back(*it);
} else {
break;
}
}
for (auto p : to_erase) {
se.erase(p);
}
}
}
}
void decompose(int v) {
find_sizes(v, v);
int centroid = find_centroid(v, v, sz[v]);
find_sizes(centroid, centroid);
blocked[centroid] = true;
for (int rep = 0; rep < 2; ++rep) {
set<pair<int, int>> se;
for (int u : g[centroid]) {
if (blocked[u]) {
continue;
}
vector<pair<int, int>> vec;
dfs(u, u, 1, vec);
for (int i = 0; i < (int) vec.size(); ++i) {
auto [sub, dep] = vec[i];
auto it = se.lower_bound(make_pair(sub, -1));
if (it != se.end()) {
ans[sub] = max(ans[sub], dep + it->second);
}
}
vec.emplace_back(sz[u] + 1, 0);//centroid
merge(se, vec);
}
reverse(g[centroid].begin(), g[centroid].end());
}
for (int u : g[v]) {
if (!blocked[u]) {
decompose(u);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
decompose(1);
for (int i = n; i >= 1; --i) {
ans[i] = max(ans[i], ans[i + 1]);
}
for (int i = 1; i <= n; ++i) {
cout << (i % 2 ? 1 : ans[i / 2] + 1) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
