#include <bits/stdc++.h>
using namespace std;
int s[200005], l[200005][19], d[200005], c[200005], dd[200005], da[200005], z = 0, ff[200005];
vector<int> g[200005];
vector<pair<int, int>> gg[200005];
set<int> t;
void dfs(int x, int p) {
s[x] = 1;
dd[x] = ++z;
l[x][0] = p;
for (int w : g[x]) {
if (w == p) continue;
c[x]++;
d[w] = d[x] + 1;
dfs(w, x);
s[x] += s[w];
}
if (p != 0 && g[x].size() == 1) t.insert(x);
da[x] = z;
}
int lca(int x, int y) {
if (d[x] < d[y]) swap(x, y);
int k = d[x] - d[y];
for (int i = 18; i >= 0; i--) {
if (k & (1 << i)) {
x = l[x][i];
}
}
if (x == y) return x;
for (int i = 18; i >= 0; i--) {
if (l[x][i] != l[y][i]) {
x = l[x][i];
y = l[y][i];
}
}
return l[x][0];
}
bool cmp(int x, int y) {
return dd[x] < dd[y];
}
int ma = 1;
void dfs2(int x, int p) {
if (p != -1 && g[x].size() == 1) {
ff[x] = 0;
return;
}
ff[x] = 0;
for (auto w : gg[x]) {
if (w.first == p) continue;
//cout << x << " " << w.first << " " << w.second << '\n';
dfs2(w.first, x);
ma = max(ma, ff[w.first] + ff[x] + w.second + 1);
ff[x] = max(ff[x], ff[w.first] + w.second);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= 18; i++) {
for (int j = 1; j <= n; j++) {
l[j][i] = l[l[j][i - 1]][i - 1];
}
}
for (int i = 1; i <= n; i++) {
if (i & 1) {
cout << 1 << '\n';
continue;
}
vector<int> v, vb, vv, va;
ma = 1;
for (int w : t) {
if (n - s[w] < i / 2) continue;
int res = 0, k = w;
for (int j = 18; j >= 0; j--) {
if (l[k][j] == 0) continue;
if (n - s[l[k][j]] >= i / 2) {
k = l[k][j];
res += (1 << j);
}
}
ma = max(ma, res + 2);
//cout << w << " " << k << '\n';
v.push_back(w);
vb.push_back(w);
}
sort(vb.begin(), vb.end(), cmp);
for (int i = 1; i < vb.size(); i++) v.push_back(lca(vb[i], vb[i - 1]));
sort(v.begin(), v.end(), cmp);
int h = 0;
stack<int> ss;
for (int w : v) {
if (w == h) continue;
h = w;
while (!ss.empty()) {
int p = ss.top();
if (dd[p] <= dd[w] && da[w] <= da[p]) {
gg[p].push_back({w, d[w] - d[p]});
break;
}
ss.pop();
}
ss.push(h);
}
while (ss.size() > 1) ss.pop();
dfs2(ss.top(), -1);
for (int w : vb) {
if (s[w] == i / 2) {
vv.push_back(w);
c[l[w][0]]--;
if (c[l[w][0]] == 0) va.push_back(l[w][0]);
}
}
for (int w : v) gg[w].clear();
for (int w : vv) t.erase(w);
for (int w : va) t.insert(w);
cout << ma << '\n';
}
}
Compilation message
meetings2.cpp: In function 'int main()':
meetings2.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int i = 1; i < vb.size(); i++) v.push_back(lca(vb[i], vb[i - 1]));
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 2 |
Correct |
3 ms |
17244 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 4 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 5 |
Runtime error |
17 ms |
34140 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 2 |
Correct |
3 ms |
17244 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 4 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 5 |
Runtime error |
17 ms |
34140 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 2 |
Correct |
3 ms |
17244 KB |
Output is correct |
| 3 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 4 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 5 |
Runtime error |
17 ms |
34140 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
