#include "bits/stdc++.h"
using namespace std;
#define ar array
const int N = 2e5 + 5;
vector<int> edges[N], S[N];
int used[N], ss[N], rr[N];
int sub[N], n, d[N];
void dff(int u, int p = -1){
ss[u] = 1;
for(auto x : edges[u]){
if(x == p) continue;
dff(x, u);
ss[u] += ss[x];
}
}
void dfs(int u, int& C, int n, int p = -1){
sub[u] = 1;
if(p == -1) d[u] = 0;
for(auto x : edges[u]){
if(x == p) continue;
if(!used[x]){
d[x] = d[u] + 1;
dfs(x, C, n, u);
sub[u] += sub[x];
} else {
if(ss[u] > ss[x]) sub[u] += ss[x];
else sub[u] += (::n - ss[u]);
}
}
if(sub[u] > n / 2 && C == -1) C = u;
}
void get(int u, vector<int>& tt, int p = -1){
tt.push_back(u);
for(auto x : edges[u]){
if(used[x] || x == p) continue;
get(x, tt, u);
}
}
struct ST{
int tree[N << 2];
void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx) { tree[x] = v; return; }
int m = (lx + rx) >> 1;
if(i <= m) sett(i, v, lx, m, x<<1);
else sett(i, v, m+1, rx, x<<1|1);
tree[x] = max(tree[x<<1], tree[x<<1|1]);
}
void umax(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx) { tree[x] = max(tree[x], v); return; }
int m = (lx + rx) >> 1;
if(i <= m) umax(i, v, lx, m, x<<1);
else umax(i, v, m+1, rx, x<<1|1);
tree[x] = max(tree[x<<1], tree[x<<1|1]);
}
int get(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return -1e9;
if(lx >= l && rx <= r) return tree[x];
int m = (lx + rx) >> 1;
return max(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
}
}tree;
void dec(int u, int n){
int C = -1;
dfs(u, C, n), dfs(C, C, n);
vector<int> tot;
for(auto v : edges[C]){
if(used[v]) continue;
S[v].clear(); get(v, S[v], C);
for(auto x : S[v]){
//~ cout<<x<<" "<<sub[x]<<" "<<d[x]<<endl;
rr[sub[x]] = max(rr[sub[x]], tree.get(sub[x], N) + d[x] + 1);
rr[min(sub[x], sub[C] - (int)S[v].size())] =
max(rr[min(sub[x], sub[C] - (int)S[v].size())], d[x] + 1);
} for(auto x : S[v]) tree.umax(sub[x], d[x]), tot.push_back(x);
} for(auto x : tot) tree.sett(sub[x], -1e9);
reverse(edges[C].begin(), edges[C].end());
for(auto v : edges[C]){
if(used[v]) continue;
for(auto x : S[v]){
rr[sub[x]] = max(rr[sub[x]], tree.get(sub[x], N) + d[x] + 1);
} for(auto x : S[v]) tree.umax(sub[x], d[x]);
} for(auto x : tot) tree.sett(sub[x], -1e9);
used[C] = 1;
for(auto x : edges[C]){
if(used[x]) continue;
dec(x, (int)S[x].size());
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
memset(tree.tree, 128, sizeof tree.tree);
cin>>n;
for(int i=1;i<n;i++){
int a, b; cin>>a>>b;
edges[a].push_back(b);
edges[b].push_back(a);
}
rr[n] = 1;
dff(1);
dec(1, n);
for(int i=n;i>0;i--) rr[i] = max(rr[i], rr[i+1]);
for(int i=1;i<=n;i++){
if(i&1) cout<<1<<"\n";
else cout<<rr[i/2]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12748 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12748 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12748 KB |
Output is correct |
| 4 |
Correct |
6 ms |
12748 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
12860 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12748 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12748 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12748 KB |
Output is correct |
| 4 |
Correct |
6 ms |
12748 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
12860 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12748 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12748 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12748 KB |
Output is correct |
| 4 |
Correct |
6 ms |
12748 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
12860 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
