#include "bits/stdc++.h"
using namespace std;
#define ar array
const int N = 2e5 + 5;
vector<int> edges[N], cnt[N];
int sub[N], par[N][20], d[N];
int tin[N], tout[N], t;
void dfs(int u, int& C, int n, int p = -1){
tin[u] = ++t, sub[u] = 1;
for(int i=1;i<20;i++) par[u][i] = par[par[u][i-1]][i-1];
for(auto x : edges[u]){
if(x == p) continue;
d[x] = d[u] + 1;
par[x][0] = u;
dfs(x, C, n, u);
sub[u] += sub[x];
}
if(sub[u] > n / 2 && C == -1) C = u;
tout[u] = t;
}
bool is(int a, int b){ return (tin[a] <= tin[b] && tout[b] <= tout[a]); }
int dis(int a, int b){
//~ cout<<a<<" "<<b<<endl;
if(is(a, b)) return d[b] - d[a];
if(is(b, a)) return d[a] - d[b];
int D = d[a] + d[b];
for(int j=19;~j;j--){
if(!is(par[a][j], b)) a = par[a][j];
} a = par[a][0];
return D - d[a] * 2;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; 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);
}
int C = -1;
par[1][0] = 1;
dfs(1, C, n);
vector<int> rr(n + 1);
int a = C, b = C, d = 0;
//~ cout<<C<<endl;
par[C][0] = C;
dfs(C, C, n);
for(int i=1;i<=n;i++){
cnt[sub[i]].push_back(i);
}
for(int i=n/2;i>0;i--){
for(auto x : cnt[i]){
//~ cout<<x<<" "<<a<<" "<<b<<" "<<d<<endl;;
int da = dis(a, x), db = dis(b, x);
if(da < db) swap(da, db), swap(a, b);
if(da > d){
assert(da == d + 1);
d = da, b = x;
} else if(db > d){
assert(db == d + 1);
d = db, a = x;
}
}
rr[i] = d + 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 |
5 ms |
9676 KB |
Output is correct |
2 |
Correct |
5 ms |
9676 KB |
Output is correct |
3 |
Correct |
4 ms |
9676 KB |
Output is correct |
4 |
Correct |
4 ms |
9676 KB |
Output is correct |
5 |
Correct |
5 ms |
9660 KB |
Output is correct |
6 |
Correct |
5 ms |
9676 KB |
Output is correct |
7 |
Correct |
5 ms |
9680 KB |
Output is correct |
8 |
Correct |
5 ms |
9676 KB |
Output is correct |
9 |
Correct |
5 ms |
9648 KB |
Output is correct |
10 |
Correct |
5 ms |
9676 KB |
Output is correct |
11 |
Correct |
5 ms |
9676 KB |
Output is correct |
12 |
Correct |
5 ms |
9676 KB |
Output is correct |
13 |
Correct |
5 ms |
9676 KB |
Output is correct |
14 |
Correct |
5 ms |
9620 KB |
Output is correct |
15 |
Correct |
4 ms |
9676 KB |
Output is correct |
16 |
Correct |
5 ms |
9728 KB |
Output is correct |
17 |
Correct |
5 ms |
9676 KB |
Output is correct |
18 |
Correct |
5 ms |
9676 KB |
Output is correct |
19 |
Correct |
5 ms |
9676 KB |
Output is correct |
20 |
Correct |
5 ms |
9656 KB |
Output is correct |
21 |
Correct |
6 ms |
9676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9676 KB |
Output is correct |
2 |
Correct |
5 ms |
9676 KB |
Output is correct |
3 |
Correct |
4 ms |
9676 KB |
Output is correct |
4 |
Correct |
4 ms |
9676 KB |
Output is correct |
5 |
Correct |
5 ms |
9660 KB |
Output is correct |
6 |
Correct |
5 ms |
9676 KB |
Output is correct |
7 |
Correct |
5 ms |
9680 KB |
Output is correct |
8 |
Correct |
5 ms |
9676 KB |
Output is correct |
9 |
Correct |
5 ms |
9648 KB |
Output is correct |
10 |
Correct |
5 ms |
9676 KB |
Output is correct |
11 |
Correct |
5 ms |
9676 KB |
Output is correct |
12 |
Correct |
5 ms |
9676 KB |
Output is correct |
13 |
Correct |
5 ms |
9676 KB |
Output is correct |
14 |
Correct |
5 ms |
9620 KB |
Output is correct |
15 |
Correct |
4 ms |
9676 KB |
Output is correct |
16 |
Correct |
5 ms |
9728 KB |
Output is correct |
17 |
Correct |
5 ms |
9676 KB |
Output is correct |
18 |
Correct |
5 ms |
9676 KB |
Output is correct |
19 |
Correct |
5 ms |
9676 KB |
Output is correct |
20 |
Correct |
5 ms |
9656 KB |
Output is correct |
21 |
Correct |
6 ms |
9676 KB |
Output is correct |
22 |
Correct |
8 ms |
10188 KB |
Output is correct |
23 |
Correct |
8 ms |
10188 KB |
Output is correct |
24 |
Correct |
8 ms |
10188 KB |
Output is correct |
25 |
Correct |
8 ms |
10276 KB |
Output is correct |
26 |
Correct |
7 ms |
10272 KB |
Output is correct |
27 |
Correct |
8 ms |
10188 KB |
Output is correct |
28 |
Correct |
9 ms |
10316 KB |
Output is correct |
29 |
Correct |
8 ms |
10240 KB |
Output is correct |
30 |
Correct |
8 ms |
10188 KB |
Output is correct |
31 |
Correct |
8 ms |
10188 KB |
Output is correct |
32 |
Correct |
9 ms |
10444 KB |
Output is correct |
33 |
Correct |
8 ms |
10572 KB |
Output is correct |
34 |
Correct |
8 ms |
10304 KB |
Output is correct |
35 |
Correct |
8 ms |
10300 KB |
Output is correct |
36 |
Correct |
9 ms |
10316 KB |
Output is correct |
37 |
Correct |
7 ms |
10188 KB |
Output is correct |
38 |
Correct |
8 ms |
10316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9676 KB |
Output is correct |
2 |
Correct |
5 ms |
9676 KB |
Output is correct |
3 |
Correct |
4 ms |
9676 KB |
Output is correct |
4 |
Correct |
4 ms |
9676 KB |
Output is correct |
5 |
Correct |
5 ms |
9660 KB |
Output is correct |
6 |
Correct |
5 ms |
9676 KB |
Output is correct |
7 |
Correct |
5 ms |
9680 KB |
Output is correct |
8 |
Correct |
5 ms |
9676 KB |
Output is correct |
9 |
Correct |
5 ms |
9648 KB |
Output is correct |
10 |
Correct |
5 ms |
9676 KB |
Output is correct |
11 |
Correct |
5 ms |
9676 KB |
Output is correct |
12 |
Correct |
5 ms |
9676 KB |
Output is correct |
13 |
Correct |
5 ms |
9676 KB |
Output is correct |
14 |
Correct |
5 ms |
9620 KB |
Output is correct |
15 |
Correct |
4 ms |
9676 KB |
Output is correct |
16 |
Correct |
5 ms |
9728 KB |
Output is correct |
17 |
Correct |
5 ms |
9676 KB |
Output is correct |
18 |
Correct |
5 ms |
9676 KB |
Output is correct |
19 |
Correct |
5 ms |
9676 KB |
Output is correct |
20 |
Correct |
5 ms |
9656 KB |
Output is correct |
21 |
Correct |
6 ms |
9676 KB |
Output is correct |
22 |
Correct |
8 ms |
10188 KB |
Output is correct |
23 |
Correct |
8 ms |
10188 KB |
Output is correct |
24 |
Correct |
8 ms |
10188 KB |
Output is correct |
25 |
Correct |
8 ms |
10276 KB |
Output is correct |
26 |
Correct |
7 ms |
10272 KB |
Output is correct |
27 |
Correct |
8 ms |
10188 KB |
Output is correct |
28 |
Correct |
9 ms |
10316 KB |
Output is correct |
29 |
Correct |
8 ms |
10240 KB |
Output is correct |
30 |
Correct |
8 ms |
10188 KB |
Output is correct |
31 |
Correct |
8 ms |
10188 KB |
Output is correct |
32 |
Correct |
9 ms |
10444 KB |
Output is correct |
33 |
Correct |
8 ms |
10572 KB |
Output is correct |
34 |
Correct |
8 ms |
10304 KB |
Output is correct |
35 |
Correct |
8 ms |
10300 KB |
Output is correct |
36 |
Correct |
9 ms |
10316 KB |
Output is correct |
37 |
Correct |
7 ms |
10188 KB |
Output is correct |
38 |
Correct |
8 ms |
10316 KB |
Output is correct |
39 |
Correct |
273 ms |
36792 KB |
Output is correct |
40 |
Correct |
270 ms |
35876 KB |
Output is correct |
41 |
Correct |
261 ms |
36768 KB |
Output is correct |
42 |
Correct |
284 ms |
37180 KB |
Output is correct |
43 |
Correct |
300 ms |
37088 KB |
Output is correct |
44 |
Correct |
283 ms |
37336 KB |
Output is correct |
45 |
Correct |
389 ms |
44724 KB |
Output is correct |
46 |
Correct |
351 ms |
49976 KB |
Output is correct |
47 |
Correct |
226 ms |
37672 KB |
Output is correct |
48 |
Correct |
194 ms |
37816 KB |
Output is correct |
49 |
Correct |
267 ms |
37900 KB |
Output is correct |
50 |
Correct |
199 ms |
37564 KB |
Output is correct |
51 |
Correct |
259 ms |
47556 KB |
Output is correct |