#include <bits/stdc++.h>
#define N 200005
#define INF 1000000000
using namespace std;
int n, sz[N], dpt[N], tb[N][18];
vector<int> adj[N];
bool vs[N];
void size_DFS(int c, int p) {
sz[c] = 1;
for(int i = 1; i < 18; i ++) {
tb[c][i] = tb[tb[c][i-1]][i-1];
}
for(int i: adj[c]) {
if(i == p) continue;
dpt[i] = dpt[c]+1;
tb[i][0] = c;
size_DFS(i, c);
sz[c] += sz[i];
}
}
int jump(int a, int ds) {
for(int i = 0; i < 18; i ++) {
if(ds&1<<i) a = tb[a][i];
}
return a;
}
int LCA(int a, int b) {
if(dpt[a] != dpt[b]) {
if(dpt[a] < dpt[b]) swap(a,b);
a = jump(a, dpt[a]-dpt[b]);
}
if(a == b) return a;
for(int i = 17; i >= 0; i --) {
if(tb[a][i] != tb[b][i]) {
a = tb[a][i];
b = tb[b][i];
}
}
return tb[a][0];
}
int getSize(int c, int rt) {
int lca = LCA(c,rt);
if(lca != c) {
return sz[c];
} else {
assert(dpt[rt] > dpt[c]);
return sz[1]-sz[jump(rt,dpt[rt]-dpt[c]-1)];
}
}
int sub_sz[N];
void size_2_DFS(int c, int p) {
sub_sz[c] = 1;
for(int i: adj[c]) {
if(vs[i] || i == p) continue;
size_2_DFS(i, c);
sub_sz[c] += sub_sz[i];
}
}
int find_cent_DFS(int c, int p, int tree_sz) {
for(int i: adj[c]) {
if(i == p || vs[i] || sub_sz[i]*2<tree_sz) continue;
return find_cent_DFS(i, c, tree_sz);
}
return c;
}
struct Segtree {
vector<int> tree;
int len;
void init(int n) {
len = 1<<18;
tree = vector<int>(len*2,-INF);
}
void update(int a, int v) {
tree[a+len] = max(tree[a+len],v);
for(a = (a+len)>>1; a >= 1; a >>= 1) {
tree[a] = max(tree[a*2],tree[a*2+1]);
}
}
void erase(int a) {
tree[a+len] = -INF;
for(a = (a+len)>>1; a >= 1; a >>= 1) {
tree[a] = max(tree[a*2],tree[a*2+1]);
}
}
int query(int a, int b) {
int res = -INF;
for(a += len, b += len; a <= b; a >>= 1, b >>= 1) {
if(a&1) res = max(res, tree[a++]);
if(~b&1) res = max(res, tree[b--]);
}
return res;
}
Segtree() {}
} tree;
int ans[N], csz[N], rsz[N];
void calc_DFS(int c, int p, int rt) {
for(int i: adj[c]) {
if(i == p || vs[i]) continue;
calc_DFS(i, c, rt);
}
if(c == rt) return;
csz[c] = getSize(c, rt);
if(p == rt) {
rsz[c] = getSize(rt, c);
} else {
rsz[c] = rsz[p];
}
}
void ans_DFS(int c, int dt, int p) {
for(int i: adj[c]) {
if(vs[i] || i == p) continue;
ans_DFS(i, dt+1, c);
}
ans[csz[c]] = max(ans[csz[c]], dt+tree.query(csz[c],tree.len-1)+1);
ans[min(rsz[c],csz[c])] = max(ans[min(rsz[c],csz[c])], dt+1);
}
void upd_DFS(int c, int dt, int p) {
for(int i: adj[c]) {
if(vs[i] || i == p) continue;
upd_DFS(i, dt+1, c);
}
tree.update(csz[c], dt);
}
void ers_DFS(int c, int dt, int p) {
for(int i: adj[c]) {
if(vs[i] || i == p) continue;
ers_DFS(i, dt+1, c);
}
tree.erase(csz[c]);
}
void centroid_DFS(int c) {
size_2_DFS(c, -1);
int cent = find_cent_DFS(c, -1, sub_sz[c]);
vs[cent] = 1;
calc_DFS(cent, -1, cent);
for(int j = 0; j < 2; j ++) {
for(int i: adj[cent]) {
if(vs[i]) continue;
ans_DFS(i, 1, cent);
upd_DFS(i, 1, cent);
}
for(int i: adj[cent]) {
if(vs[i]) continue;
ers_DFS(i, 1, cent);
}
reverse(adj[cent].begin(),adj[cent].end());
}
for(int i: adj[cent]) {
if(vs[i]) continue;
centroid_DFS(i);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
tree.init(n);
for(int i = 1, u, v; i < n; i ++) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
size_DFS(1,-1);
centroid_DFS(1);
for(int i = n/2; i >= 1; i --) {
ans[i] = max({ans[i], ans[i+1], 1});
}
for(int i = 1; i <= n; i ++) {
if(i%2) cout << "1\n";
else cout << ans[i/2] << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
3 ms |
10672 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
3 ms |
10672 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
3 ms |
10672 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
