#include<bits/stdc++.h>
using namespace std;
const int nax = 2e5 + 3;
vector<int>g[nax];
int n;
int sub[nax];
bool r[nax];
vector<pair<int,int>>stk;
int ans[nax];
int dfs(int v, int p = 0) {
sub[v] = 1;
for(int u : g[v]) if(u!=p && !r[u]) {
sub[v] += dfs(u, v);
}
return sub[v];
}
int get_centroid(int v, int sz, int p = 0) {
for(int u : g[v]) if(u!=p && !r[u]) {
if(sub[u] * 2 > sz) {
return get_centroid(u, sz, v);
}
}
return v;
}
void dfs2(int v, int p, int d) {
stk.emplace_back(sub[v], d);
for(int u : g[v]) if(u!=p && !r[u]) {
dfs2(u, v, d+1);
}
}
void centroid(int v) {
int C = get_centroid(v, dfs(v));
dfs(C);
//do here
for(int t : {1, 2}) {
set<pair<int,int>>pr = {{sub[C], 0}};
for(int u : g[C]) if(!r[u]) {
stk.clear();
dfs2(u, C, 1);
for(auto [sz, d] : stk) {
// query
auto it = pr.lower_bound(make_pair(sz, -1));
if(it!=pr.end()) {
ans[sz * 2] = max(ans[sz * 2], it->second+d+1);
//f(C==2) cerr<<sz*2<<' '<<it->second+d+1<<'\n';
}
}
for(auto [sz, d] : stk) {
// insert
auto it = pr.lower_bound(make_pair(sz, -1));
if(it!=pr.end() && it->first>=sz && it->second>=d) continue;
while(1) {
it = pr.upper_bound(make_pair(sz, 1e9));
if(it==pr.begin()) break;
--it;
if(it->second<=d) {
pr.erase(it);
} else break;
}
pr.insert({sz, d});
}
}
reverse(g[C].begin(), g[C].end());
}
r[C] = 1;
for(int u : g[C]) if(!r[u]) {
centroid(u);
}
}
void PlayGround() {
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);
}
centroid(1);
int mx = 1;
for(int i=n; i>0; --i) {
mx = max(mx, ans[i]);
ans[i] = mx;
}
for(int i=1; i<=n; ++i) {
if(i&1) cout<<"1\n";
else cout<<ans[i]<<'\n';
}
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
Compilation message
meetings2.cpp: In function 'void centroid(int)':
meetings2.cpp:38:10: warning: unused variable 't' [-Wunused-variable]
38 | for(int t : {1, 2}) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5032 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5040 KB |
Output is correct |
5 |
Correct |
3 ms |
5036 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
4 ms |
5032 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
4 ms |
5028 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
5036 KB |
Output is correct |
16 |
Correct |
3 ms |
5036 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
5036 KB |
Output is correct |
20 |
Correct |
3 ms |
5032 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5032 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5040 KB |
Output is correct |
5 |
Correct |
3 ms |
5036 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
4 ms |
5032 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
4 ms |
5028 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
5036 KB |
Output is correct |
16 |
Correct |
3 ms |
5036 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
5036 KB |
Output is correct |
20 |
Correct |
3 ms |
5032 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
8 ms |
5172 KB |
Output is correct |
23 |
Correct |
8 ms |
5268 KB |
Output is correct |
24 |
Correct |
8 ms |
5264 KB |
Output is correct |
25 |
Correct |
9 ms |
5180 KB |
Output is correct |
26 |
Correct |
7 ms |
5172 KB |
Output is correct |
27 |
Correct |
8 ms |
5176 KB |
Output is correct |
28 |
Correct |
8 ms |
5204 KB |
Output is correct |
29 |
Correct |
8 ms |
5172 KB |
Output is correct |
30 |
Correct |
7 ms |
5172 KB |
Output is correct |
31 |
Correct |
7 ms |
5204 KB |
Output is correct |
32 |
Correct |
13 ms |
5304 KB |
Output is correct |
33 |
Correct |
14 ms |
5460 KB |
Output is correct |
34 |
Correct |
6 ms |
5332 KB |
Output is correct |
35 |
Correct |
5 ms |
5204 KB |
Output is correct |
36 |
Correct |
9 ms |
5292 KB |
Output is correct |
37 |
Correct |
5 ms |
5204 KB |
Output is correct |
38 |
Correct |
9 ms |
5332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5032 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5040 KB |
Output is correct |
5 |
Correct |
3 ms |
5036 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
4 ms |
5032 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
4 ms |
5028 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
5036 KB |
Output is correct |
16 |
Correct |
3 ms |
5036 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
5036 KB |
Output is correct |
20 |
Correct |
3 ms |
5032 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
8 ms |
5172 KB |
Output is correct |
23 |
Correct |
8 ms |
5268 KB |
Output is correct |
24 |
Correct |
8 ms |
5264 KB |
Output is correct |
25 |
Correct |
9 ms |
5180 KB |
Output is correct |
26 |
Correct |
7 ms |
5172 KB |
Output is correct |
27 |
Correct |
8 ms |
5176 KB |
Output is correct |
28 |
Correct |
8 ms |
5204 KB |
Output is correct |
29 |
Correct |
8 ms |
5172 KB |
Output is correct |
30 |
Correct |
7 ms |
5172 KB |
Output is correct |
31 |
Correct |
7 ms |
5204 KB |
Output is correct |
32 |
Correct |
13 ms |
5304 KB |
Output is correct |
33 |
Correct |
14 ms |
5460 KB |
Output is correct |
34 |
Correct |
6 ms |
5332 KB |
Output is correct |
35 |
Correct |
5 ms |
5204 KB |
Output is correct |
36 |
Correct |
9 ms |
5292 KB |
Output is correct |
37 |
Correct |
5 ms |
5204 KB |
Output is correct |
38 |
Correct |
9 ms |
5332 KB |
Output is correct |
39 |
Correct |
563 ms |
16960 KB |
Output is correct |
40 |
Correct |
505 ms |
16524 KB |
Output is correct |
41 |
Correct |
532 ms |
16704 KB |
Output is correct |
42 |
Correct |
503 ms |
17008 KB |
Output is correct |
43 |
Correct |
532 ms |
17220 KB |
Output is correct |
44 |
Correct |
521 ms |
16916 KB |
Output is correct |
45 |
Correct |
1423 ms |
23476 KB |
Output is correct |
46 |
Correct |
1376 ms |
29632 KB |
Output is correct |
47 |
Correct |
179 ms |
16488 KB |
Output is correct |
48 |
Correct |
120 ms |
16560 KB |
Output is correct |
49 |
Correct |
631 ms |
17784 KB |
Output is correct |
50 |
Correct |
157 ms |
17560 KB |
Output is correct |
51 |
Correct |
748 ms |
25652 KB |
Output is correct |