#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e5 + 5;
vector<int> g[nmax];
int n;
int rez[nmax];
namespace Centroid {
int occ[nmax];
int area[nmax];
int nval[nmax];
int depth[nmax];
#define norm lasama
map<pair<int, int> ,int> norm;
map<int ,int> fpoz;
namespace AINT {
int aint[1048576];
static int len;
void init(int nlen) { len = nlen; }
void upd(int poz, int val, int node = 1, int cl = 1, int cr = len) {
if(cl == cr)
aint[node] = val;
else {
int mid = cl + cr >> 1;
if(poz <= mid)
upd(poz, val, 2 * node, cl, mid);
else
upd(poz, val, 2 * node + 1, mid + 1, cr);
aint[node] = max(aint[2 * node], aint[2 * node + 1]);
}
return;
}
int query(int poz, int node = 1, int cl = 1, int cr = len) {
if(cr < poz)
return 0;
if(poz <= cl)
return aint[node];
int mid = cl + cr >> 1;
return max(query(poz, 2 * node, cl, mid), query(poz, 2 * node + 1, mid + 1, cr));
}
};
void initcentr(int node, int f) {
area[node] = 1;
for(auto x : g[node]) {
if(occ[x] == 0 && x != f)
initcentr(x, node), area[node] += area[x];
}
return;
}
int initdepth(int node, int f) {
if(occ[node])
return area[node];
depth[node] = depth[f] + 1;
area[node] = 1;
for(auto x : g[node])
if(x != f)
area[node] += initdepth(x, node);
return area[node];
}
int findcentr(int node, int f, int thresh) {
for(auto x : g[node]) {
if(occ[x] || x == f)
continue;
if(area[x] > thresh)
return findcentr(x, node, thresh);
}
return node;
}
void aggr(int node, int f, int val) {
if(val == -1)
AINT::upd(nval[node], 0);
else
AINT::upd(nval[node], depth[node]);
for(auto x : g[node])
if(!occ[x] && x != f)
aggr(x, node, val);
}
void bnorm(int node, int f) {
norm[{area[node], node}];
for(auto x : g[node]) if(!occ[x] && x != f) bnorm(x, node);
return;
}
void anorm(int node, int f) {
nval[node] = norm[{area[node], node}];
//cerr << node << ' ' << area[node] << ' ' << nval[node] << ' ' << depth[node] << '\n';
for(auto x : g[node]) if(!occ[x] && x != f) anorm(x, node);
return;
}
void query(int node, int f) {
rez[(area[node]) * 2] = max(rez[(area[node]) * 2], AINT::query(fpoz[area[node]]) + depth[node] - 1);
for(auto x : g[node]) if(!occ[x] && x != f) query(x, node);
return;
}
void mkcentr(int node) {
//cerr << "++++++\n" << node << "\n=====\n";
int temp;
initcentr(node, node);
node = findcentr(node, node, area[node] / 2);
//cerr << "Centroid is: " << node << '\n';
depth[node] = 0;
initdepth(node, node);
for(int x, i = 0; i < g[node].size(); i++) {
if(occ[g[node][i]]) {
swap(g[node][i], g[node].back());
g[node].pop_back();
i--;
continue;
}
x = g[node][i];
norm[{n - area[x], node}];
bnorm(x, node);
}
temp = 0;
for(auto &[a, b] : norm) {
b = ++temp;
if(fpoz.find(a.first) == fpoz.end())
fpoz[a.first] = b;
}
AINT::init(temp);
for(auto x : g[node])
anorm(x, node);
for(auto x : g[node])
aggr(x, node, 1);
for(auto x : g[node]) {
aggr(x, node, -1);
AINT::upd(temp = norm[{n - area[x], node}], depth[node]);
query(x, node);
AINT::upd(temp, 0);
aggr(x, node, 1);
}
for(auto x : g[node])
aggr(x, node, -1);
fpoz.clear();
norm.clear();
occ[node] = 1;
for(auto x : g[node])
mkcentr(x);
}
}
int main() {
cin >> n;
for(int x, y, i = 1; i < n; i++) {
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
Centroid::mkcentr(1);
for(int i = n; i > 0; i--) {
if(i % 2 == 0)
rez[i] = max({1, rez[i + 1], rez[i]});
else
rez[i] = 1;
}
//cout << "1\n" << 2 + rez[2] << '\n';
for(int i = 1; i <= n; i++)
cout << rez[i] << '\n';
}
Compilation message
meetings2.cpp: In function 'void Centroid::AINT::upd(int, int, int, int, int)':
meetings2.cpp:25:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | int mid = cl + cr >> 1;
| ~~~^~~~
meetings2.cpp: In function 'int Centroid::AINT::query(int, int, int, int)':
meetings2.cpp:39:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int mid = cl + cr >> 1;
| ~~~^~~~
meetings2.cpp: In function 'void Centroid::mkcentr(int)':
meetings2.cpp:103:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int x, i = 0; i < g[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
meetings2.cpp:115:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
115 | for(auto &[a, b] : norm) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
