#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;
while(len < n) len <<= 1;
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]);
}
}
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];
void ans_DFS(int c, int dt, int p, int rt) {
for(int i: adj[c]) {
if(vs[i] || i == p) continue;
ans_DFS(i, dt+1, c, rt);
}
if(c == rt) return;
int csz = getSize(c, rt);
ans[csz] = max(ans[csz], dt+tree.query(csz,tree.len-1)+1);
int rsz = getSize(rt, c);
ans[min(rsz,csz)] = max(ans[min(rsz,csz)], dt+1);
}
void upd_DFS(int c, int dt, int p, int rt) {
for(int i: adj[c]) {
if(vs[i] || i == p) continue;
upd_DFS(i, dt+1, c, rt);
}
if(c == rt) return;
int csz = getSize(c, rt);
tree.update(csz, dt);
}
void centroid_DFS(int c) {
size_2_DFS(c, -1);
int cent = find_cent_DFS(c, -1, sub_sz[c]);
vs[cent] = 1;
tree.init(sub_sz[c]);
for(int i: adj[cent]) {
if(vs[i]) continue;
ans_DFS(i, 1, cent, cent);
upd_DFS(i, 1, cent, cent);
}
for(int i: adj[cent]) {
if(vs[i]) continue;
centroid_DFS(i);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> 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]);
}
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 |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Runtime error |
7 ms |
17176 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Runtime error |
7 ms |
17176 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Runtime error |
7 ms |
17176 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
