#include <bits/stdc++.h>
//#define int long long
using namespace std;
struct Val {
int val, i;
};
const int N = 2e5 + 42, T = 18, INF = 1e18;
Val val[N];
vector<int> adj[N];
int n, root, id = 0, sz[N], ans[N], dist[N], deb[N], fin[N], bl[T][N];
int DFS(int i, int pre) {
int maxi = 0, sum = 1;
for(int j : adj[i])
if(j != pre) {
int val = DFS(j, i);
sum += val;
maxi = max(maxi, val);
}
maxi = max(maxi, n - sum);
if(maxi <= n/2)
root = i;
return sum;
}
int getSz(int i, int pre) {
sz[i] = 1;
deb[i] = id++;
bl[0][i] = pre;
dist[i] = dist[pre] + 1;
for(int j : adj[i])
if(j != pre)
sz[i] += getSz(j, i);
fin[i] = id++;
return sz[i];
}
inline bool ancester(int a, int b) {
return deb[a] <= deb[b] && fin[b] <= fin[a];
}
int LCA(int a, int b) {
if(dist[a] < dist[b])
swap(a, b);
if(ancester(b, a))
return b;
for(int i = T-1; i > -1; i--)
while(!ancester(bl[i][a], b)) {
a = bl[i][a];
if(dist[a] < dist[b])
swap(a, b);
}
return bl[0][a];
}
inline int distance(int a, int b) {
return dist[a] + dist[b] - 2 * dist[LCA(a, b)];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
a--, b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
DFS(0, 0);
getSz(root, root);
for(int i = 0; i < n; i++) {
val[i].i = i;
val[i].val = sz[i];
}
sort(val, val + n,
[](Val a, Val b) {
return a.val > b.val;
});
for(int i = 1; i < T; i++)
for(int j = 0; j < n; j++)
bl[i][j] = bl[i-1][bl[i-1][j]];
int diam1 = root, diam2 = root;
for(int i = 1; i < n; i++) {
int dist1 = ans[val[i-1].val],
dist2 = distance(diam1, val[i].i),
dist3 = distance(val[i].i, diam2);
ans[val[i].val] = max(max(dist1, dist2), dist3);
if(dist2 == ans[val[i].val])
diam2 = val[i].i;
else if(dist3 == ans[val[i].val])
diam1 = val[i].i;
}
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 == 1)
cout << "1\n";
else
cout << ans[i/2] + 1 << '\n';
}
Compilation message
meetings2.cpp:9:39: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
9 | const int N = 2e5 + 42, T = 18, INF = 1e18;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5844 KB |
Output is correct |
2 |
Correct |
4 ms |
5844 KB |
Output is correct |
3 |
Correct |
4 ms |
5888 KB |
Output is correct |
4 |
Correct |
3 ms |
5844 KB |
Output is correct |
5 |
Correct |
4 ms |
5844 KB |
Output is correct |
6 |
Correct |
3 ms |
5844 KB |
Output is correct |
7 |
Correct |
4 ms |
5844 KB |
Output is correct |
8 |
Correct |
4 ms |
5844 KB |
Output is correct |
9 |
Correct |
4 ms |
5844 KB |
Output is correct |
10 |
Correct |
4 ms |
5844 KB |
Output is correct |
11 |
Correct |
4 ms |
5844 KB |
Output is correct |
12 |
Correct |
4 ms |
5844 KB |
Output is correct |
13 |
Correct |
4 ms |
5844 KB |
Output is correct |
14 |
Correct |
5 ms |
5844 KB |
Output is correct |
15 |
Correct |
4 ms |
5844 KB |
Output is correct |
16 |
Correct |
4 ms |
5844 KB |
Output is correct |
17 |
Correct |
5 ms |
5844 KB |
Output is correct |
18 |
Correct |
5 ms |
5924 KB |
Output is correct |
19 |
Correct |
4 ms |
5844 KB |
Output is correct |
20 |
Correct |
4 ms |
5844 KB |
Output is correct |
21 |
Correct |
4 ms |
5844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5844 KB |
Output is correct |
2 |
Correct |
4 ms |
5844 KB |
Output is correct |
3 |
Correct |
4 ms |
5888 KB |
Output is correct |
4 |
Correct |
3 ms |
5844 KB |
Output is correct |
5 |
Correct |
4 ms |
5844 KB |
Output is correct |
6 |
Correct |
3 ms |
5844 KB |
Output is correct |
7 |
Correct |
4 ms |
5844 KB |
Output is correct |
8 |
Correct |
4 ms |
5844 KB |
Output is correct |
9 |
Correct |
4 ms |
5844 KB |
Output is correct |
10 |
Correct |
4 ms |
5844 KB |
Output is correct |
11 |
Correct |
4 ms |
5844 KB |
Output is correct |
12 |
Correct |
4 ms |
5844 KB |
Output is correct |
13 |
Correct |
4 ms |
5844 KB |
Output is correct |
14 |
Correct |
5 ms |
5844 KB |
Output is correct |
15 |
Correct |
4 ms |
5844 KB |
Output is correct |
16 |
Correct |
4 ms |
5844 KB |
Output is correct |
17 |
Correct |
5 ms |
5844 KB |
Output is correct |
18 |
Correct |
5 ms |
5924 KB |
Output is correct |
19 |
Correct |
4 ms |
5844 KB |
Output is correct |
20 |
Correct |
4 ms |
5844 KB |
Output is correct |
21 |
Correct |
4 ms |
5844 KB |
Output is correct |
22 |
Correct |
6 ms |
6356 KB |
Output is correct |
23 |
Correct |
5 ms |
6404 KB |
Output is correct |
24 |
Correct |
7 ms |
6332 KB |
Output is correct |
25 |
Correct |
6 ms |
6396 KB |
Output is correct |
26 |
Correct |
6 ms |
6356 KB |
Output is correct |
27 |
Correct |
6 ms |
6356 KB |
Output is correct |
28 |
Correct |
6 ms |
6356 KB |
Output is correct |
29 |
Correct |
6 ms |
6356 KB |
Output is correct |
30 |
Correct |
6 ms |
6356 KB |
Output is correct |
31 |
Correct |
7 ms |
6428 KB |
Output is correct |
32 |
Correct |
9 ms |
6508 KB |
Output is correct |
33 |
Correct |
6 ms |
6484 KB |
Output is correct |
34 |
Correct |
6 ms |
6356 KB |
Output is correct |
35 |
Correct |
7 ms |
6356 KB |
Output is correct |
36 |
Correct |
9 ms |
6356 KB |
Output is correct |
37 |
Correct |
6 ms |
6448 KB |
Output is correct |
38 |
Correct |
5 ms |
6484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5844 KB |
Output is correct |
2 |
Correct |
4 ms |
5844 KB |
Output is correct |
3 |
Correct |
4 ms |
5888 KB |
Output is correct |
4 |
Correct |
3 ms |
5844 KB |
Output is correct |
5 |
Correct |
4 ms |
5844 KB |
Output is correct |
6 |
Correct |
3 ms |
5844 KB |
Output is correct |
7 |
Correct |
4 ms |
5844 KB |
Output is correct |
8 |
Correct |
4 ms |
5844 KB |
Output is correct |
9 |
Correct |
4 ms |
5844 KB |
Output is correct |
10 |
Correct |
4 ms |
5844 KB |
Output is correct |
11 |
Correct |
4 ms |
5844 KB |
Output is correct |
12 |
Correct |
4 ms |
5844 KB |
Output is correct |
13 |
Correct |
4 ms |
5844 KB |
Output is correct |
14 |
Correct |
5 ms |
5844 KB |
Output is correct |
15 |
Correct |
4 ms |
5844 KB |
Output is correct |
16 |
Correct |
4 ms |
5844 KB |
Output is correct |
17 |
Correct |
5 ms |
5844 KB |
Output is correct |
18 |
Correct |
5 ms |
5924 KB |
Output is correct |
19 |
Correct |
4 ms |
5844 KB |
Output is correct |
20 |
Correct |
4 ms |
5844 KB |
Output is correct |
21 |
Correct |
4 ms |
5844 KB |
Output is correct |
22 |
Correct |
6 ms |
6356 KB |
Output is correct |
23 |
Correct |
5 ms |
6404 KB |
Output is correct |
24 |
Correct |
7 ms |
6332 KB |
Output is correct |
25 |
Correct |
6 ms |
6396 KB |
Output is correct |
26 |
Correct |
6 ms |
6356 KB |
Output is correct |
27 |
Correct |
6 ms |
6356 KB |
Output is correct |
28 |
Correct |
6 ms |
6356 KB |
Output is correct |
29 |
Correct |
6 ms |
6356 KB |
Output is correct |
30 |
Correct |
6 ms |
6356 KB |
Output is correct |
31 |
Correct |
7 ms |
6428 KB |
Output is correct |
32 |
Correct |
9 ms |
6508 KB |
Output is correct |
33 |
Correct |
6 ms |
6484 KB |
Output is correct |
34 |
Correct |
6 ms |
6356 KB |
Output is correct |
35 |
Correct |
7 ms |
6356 KB |
Output is correct |
36 |
Correct |
9 ms |
6356 KB |
Output is correct |
37 |
Correct |
6 ms |
6448 KB |
Output is correct |
38 |
Correct |
5 ms |
6484 KB |
Output is correct |
39 |
Correct |
196 ms |
30980 KB |
Output is correct |
40 |
Correct |
226 ms |
30412 KB |
Output is correct |
41 |
Correct |
188 ms |
31008 KB |
Output is correct |
42 |
Correct |
210 ms |
31456 KB |
Output is correct |
43 |
Correct |
221 ms |
31460 KB |
Output is correct |
44 |
Correct |
223 ms |
31460 KB |
Output is correct |
45 |
Correct |
399 ms |
35276 KB |
Output is correct |
46 |
Correct |
232 ms |
38692 KB |
Output is correct |
47 |
Correct |
190 ms |
31748 KB |
Output is correct |
48 |
Correct |
108 ms |
31936 KB |
Output is correct |
49 |
Correct |
241 ms |
32076 KB |
Output is correct |
50 |
Correct |
148 ms |
32068 KB |
Output is correct |
51 |
Correct |
207 ms |
37844 KB |
Output is correct |