#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> g[N], seen;
int n, c, sub[N], done[N], f[N], ans[N], par[N], exc[N];
int maxi;
int upper;
void add(int x, int y) {
x = upper - x + 1;
assert(x > 0);
while (x <= upper) {
seen.push_back(x);
f[x] = max(f[x], y);
x += x & -x;
}
}
int get(int x) {
int ans = -N;
x = upper - x + 1;
while (x > 0) {
ans = max(ans, f[x]);
x -= x & -x;
}
return ans;
}
int find_centroid(int x, int p, int sz) {
for (int to : g[x]) {
if (!done[to] && to != p && sub[to] > sz / 2) {
return find_centroid(to, x, sz);
}
}
return x;
}
void calc(int x, int p) {
sub[x] = 1;
for (int to : g[x]) {
if (!done[to] && p != to) {
calc(to, x);
sub[x] += sub[to];
}
}
}
int excSize(int x, int dir) {
if (par[x] == dir) {
return exc[x];
}
return n - exc[dir];
}
void insert(int x, int p, int anc, int pos, int depth = 1) {
for (int to : g[x]) {
if (to != p && !done[to]) {
insert(to, x, anc, pos, depth + 1);
}
}
int sub_size = excSize(x, p);
if (pos == 1) {
add(sub_size, depth);
} else {
ans[sub_size] = max(ans[sub_size], depth + get(sub_size) + 1);
int v = min(sub_size, excSize(c, anc));
ans[v] = max(ans[v], depth + 1);
}
}
void find_par(int x, int p) {
par[x] = p;
exc[x] = 1;
for (int to : g[x]) {
if (to != p) {
find_par(to, x);
exc[x] += exc[to];
}
}
}
void decomp(int x, int p, int sz) {
calc(x, p);
c = find_centroid(x, -1, sz);
upper = n;
calc(c, p);
for (int to : g[c]) {
if (done[to]) continue;
insert(to, c, to, 0);
insert(to, c, to, 1);
}
for (int i : seen) f[i] = -1e9; seen.clear();
done[c] = 1;
for (int to : g[c]) {
if (!done[to]) {
decomp(to, c, sub[to]);
}
}
}
int main() {
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);
}
for (int i = 1; i <= n; ++i) {
f[i] = -1e9;
}
find_par(1, 0);
decomp(1, 0, n);
ans[n] = 1;
for (int i = n; i >= 1; --i) {
ans[i] = max(ans[i], ans[i + 1]);
}
for (int i = 1; i <= n; ++i) {
if (i % 2 == 0) {
cout << ans[i / 2] << '\n';
} else {
cout << "1\n";
}
}
}
Compilation message
meetings2.cpp: In function 'void decomp(int, int, int)':
meetings2.cpp:84:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
84 | for (int i : seen) f[i] = -1e9; seen.clear();
| ^~~
meetings2.cpp:84:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
84 | for (int i : seen) f[i] = -1e9; seen.clear();
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5000 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5000 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5000 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5000 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5000 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5000 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
