This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++)
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--)
#define ii pair<int, int>
#define fi first
#define se second
#define vi vector<int>
#define eb emplace_back
#define em emplace
#define sp ' '
#define endl '\n'
#define int long long
const int maxn =2e5 +5;
int n;
vi g[maxn];
int tim;
int tin[maxn];
int dep[maxn];
int sz[maxn];
int euler[maxn * 2];
int lca[21][maxn * 2];
vector<int> nodes_sz[maxn];
pair<int, ii> Dia;
int ans[maxn];
void dfs_sz(int u, int p) {
sz[u] = 1;
for(int v: g[u]) {
if(v - p) {
dfs_sz(v, u);
sz[u] += sz[v];
}
}
}
int get_cen(int u, int p) {
for(int v: g[u]) {
if(v - p and sz[v] * 2 > sz[1]) return get_cen(v, u);
}
return u;
}
void dfs_prep(int u, int p) {
sz[u] = 1;
++tim;
tin[u] = tim;
euler[tim] = u;
for(int v: g[u]) {
if(v - p) {
dep[v] = dep[u] + 1;
dfs_prep(v, u);
sz[u] += sz[v];
++tim;
euler[tim] = u;
}
}
}
int hg(int u, int v) {
return dep[u] < dep[v]? u: v;
}
int get_lca(int u, int v) {
int l = tin[u], r = tin[v];
if(r < l) swap(r, l);
int bit = __lg(r - l + 1);
return hg(lca[bit][l], lca[bit][r - (1 << bit) + 1]);
}
int get_dis(int u, int v) {
return dep[u] + dep[v] - 2 * dep[get_lca(u, v)];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
fori(i, 2, n) {
int u, v;
cin >> u >> v;
g[u].eb(v);
g[v].eb(u);
}
dfs_sz(1, 1);
int cen = get_cen(1, 1);
dfs_prep(cen, cen);
// cout << cen << endl;
fori(bit, 0, 20) {
fori(i, 1, tim - (1 << bit) + 1) {
lca[bit][i] = !bit? euler[i]: hg(lca[bit - 1][i], lca[bit - 1][i + (1 << bit - 1)]);
}
}
// cout << get_dis(1, 5) << endl;
fori(i, 1, n) nodes_sz[sz[i]].eb(i);
Dia = make_pair(0, ii(cen, cen));
int pt = n;
ford(j, n, 1) {
if(j & 1) ans[j] = 1;
else {
for(; pt >= j / 2; pt--) {
for(int u: nodes_sz[pt]) {
// cout << pt << ": " << u << endl;
int l = Dia.se.fi, r = Dia.se.se;
Dia = max({Dia, make_pair(get_dis(l, u), ii(l, u)), make_pair(get_dis(u, r), ii(u, r))});
}
}
ans[j] = 1 + Dia.fi;
}
}
fori(i, 1, n) cout << ans[i] << endl;
}
Compilation message (stderr)
meetings2.cpp: In function 'int main()':
meetings2.cpp:95:81: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
95 | lca[bit][i] = !bit? euler[i]: hg(lca[bit - 1][i], lca[bit - 1][i + (1 << bit - 1)]);
| ~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |