#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
const int N = 2e5 + 5;
int n;
int timer, in[N], out[N], dep[N], tot[N], ans[N], P[N][20];
vector < int > v[N];
set < int > st[N];
bool is_anc(int a, int b) {
return (in[a] <= in[b] && out[b] <= out[a]);
}
int LCA(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
if (is_anc(a, b)) return a;
for (int j = 18; j >= 0; --j)
if (!is_anc(P[a][j], b)) a = P[a][j];
return P[a][0];
}
int dst(int a, int b) {
return dep[a] + dep[b] - 2 * dep[LCA(a, b)] + 1;
}
void dfs(int x, int p) {
dep[x] = dep[p] + 1;
in[x] = ++timer;
P[x][0] = p;
for (int j = 1; j <= 18; ++j) {
P[x][j] = P[P[x][j - 1]][j - 1];
}
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i];
if (to == p) continue;
dfs(to, x);
}
out[x] = timer;
}
main () {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n;
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
v[a].pb(b);
v[b].pb(a);
st[a].insert(b);
st[b].insert(a);
}
dfs(1, 1);
queue < int > q;
for (int i = 1; i <= n; ++i) {
tot[i] = 1;
if (v[i].size() == 1) {
q.push(i);
}
}
vector < pair < int , int > > rec;
while (q.size()) {
int x = q.front();
q.pop();
if (st[x].size() == 1) {
int y = (*st[x].begin());
rec.pb({x, tot[x]});
tot[y] += tot[x];
st[y].erase(x);
st[x].erase(y);
if (st[y].size() == 1) {
q.push(y);
}
}
}
for (int i = 0; i + 1 < rec.size(); ++i) {
assert(rec[i].s <= rec[i + 1].s);
}
int str = 1;
for (int i = 1; i <= n; ++i) {
if (tot[i] == n) str = i;
}
int a0 = str, b0 = str, dm = 1;
for (int i = n; i >= 1; --i) {
if (i % 2 == 1) {
ans[i] = 1;
}
else {
while (rec.size() && rec.back().s >= i / 2) {
int x = rec.back().f, a1 = dst(a0, x), b1 = dst(b0, x);
rec.pop_back();
if (a1 <= b1) {
if (dm < b1) dm = b1, a0 = x;
}
else
if (b1 < a1) {
if (dm < a1) dm = a1, b0 = x;
}
}
ans[i] = dm;
}
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << "\n";
}
}
Compilation message
meetings2.cpp: In function 'void dfs(int, int)':
meetings2.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i = 0; i < v[x].size(); ++i) {
| ~~^~~~~~~~~~~~~
meetings2.cpp: At global scope:
meetings2.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
47 | main () {
| ^~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = 0; i + 1 < rec.size(); ++i) {
| ~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14432 KB |
Output is correct |
| 4 |
Runtime error |
19 ms |
29224 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14432 KB |
Output is correct |
| 4 |
Runtime error |
19 ms |
29224 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14432 KB |
Output is correct |
| 4 |
Runtime error |
19 ms |
29224 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
