#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int M = 2e5 + 10;
const int INF = 1e9 + 10;
int n, Sub[M], Chk[M], Dep[M];
vector<int> G[M];
struct SEG {
int T[M << 1], L[M << 1];
void init() {
for (int i = 0; i < M << 2; i++) L[i] = -2 * INF;
}
void push(int lo, int hi, int idx) {
if (L[idx] == -2 * INF) return;
if (lo != hi) {
L[idx << 1] = L[idx];
L[idx << 1 | 1] = L[idx];
}
T[idx] = L[idx]; L[idx] = -2 * INF;
}
int update(int a, int b, int x, int lo = 1, int hi = n >> 1, int idx = 1) {
push(lo, hi, idx);
if (b < lo || a > hi) return T[idx];
if (a <= lo && hi <= b) {
L[idx] = x; push(lo, hi, idx); return T[idx];
}
return T[idx] = max(update(a, b, x, lo, lo + hi >> 1, idx << 1), update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1));
}
int query(int a, int lo = 1, int hi = n >> 1, int idx = 1) {
push(lo, hi, idx);
if (lo == hi) return T[idx];
if (a <= lo + hi >> 1) return query(a, lo, lo + hi >> 1, idx << 1);
else return query(a, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
}
int find(int x, int lo = 1, int hi = n >> 1, int idx = 1) {
push(lo, hi, idx);
if (lo == hi) {
if (T[idx] >= x) return lo;
return lo - 1;
}
push(1 + (lo + hi >> 1), hi, idx << 1 | 1);
if (T[idx << 1 | 1] >= x) return find(x, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
return find(x, lo, lo + hi >> 1, idx << 1);
}
} S, Ans;
void dfs(int p, int cur) {
Sub[cur] = 1;
for (int x : G[cur]) if (p != x && !Chk[x]) {
dfs(cur, x); Sub[cur] += Sub[x];
}
}
int cent(int p, int cur, int s) {
for (int x : G[cur]) if (p != x && !Chk[x]) {
if (Sub[x] > s / 2) return cent(cur, x, s);
}
return cur;
}
void dfs2(int p, int cur) {
if (Chk[cur]) return; Sub[cur] = 1;
for (int x : G[cur]) if (p != x) {
Dep[x] = Dep[cur] + 1;
dfs2(cur, x); Sub[cur] += Sub[x];
}
}
void dp(int p, int cur) {
for (int x : G[cur]) if (p != x && !Chk[x]) {
dp(cur, x);
}
int a = S.query(Sub[cur]);
if (a == -INF) return;
int k = Ans.find(Dep[cur] + a);
Ans.update(k + 1, Sub[cur], Dep[cur] + a);
}
void update(int p, int cur) {
int k = S.find(Dep[cur]);
S.update(k + 1, Sub[cur], Dep[cur]);
for (int x : G[cur]) if (p != x && !Chk[x]) {
update(cur, x);
}
}
void solve(int cur) {
dfs(cur, cur); int k = cent(cur, cur, Sub[cur]);
Dep[k] = 0; Sub[k] = 1;
S.update(1, n, -INF);
for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
int x = G[k][i]; Dep[x] = 1;
dfs2(k, x);
int l = S.find(0);
S.update(l + 1, n - Sub[x], 0);
dp(k, x); update(k, x);
l = S.find(1);
S.update(l + 1, n - Sub[x], -INF);
}
S.update(1, n, -INF);
for (int i = G[k].size() - 1; i >= 0; i--) if (!Chk[G[k][i]]) {
int x = G[k][i];
dp(k, x); update(k, x);
}
Chk[k] = 1;
vector<int> V(G[k].size());
for (int i = 0; i < G[k].size(); i++) V[i] = Sub[G[k][i]];
for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
Sub[k] = n - V[i]; solve(G[k][i]);
}
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 1; i < n; i++) {
int x, y; cin >> x >> y;
G[x].push_back(y); G[y].push_back(x);
}
S.init(); solve(1);
for (int i = 1; i <= n; i++) {
if (i & 1) cout << 1 << '\n';
else cout << Ans.query(i / 2) + 1 << '\n';
}
}
Compilation message
meetings2.cpp: In member function 'int SEG::update(int, int, int, int, int, int)':
meetings2.cpp:33:52: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | return T[idx] = max(update(a, b, x, lo, lo + hi >> 1, idx << 1), update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1));
| ~~~^~~~
meetings2.cpp:33:98: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | return T[idx] = max(update(a, b, x, lo, lo + hi >> 1, idx << 1), update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1));
| ~~~^~~~
meetings2.cpp: In member function 'int SEG::query(int, int, int, int)':
meetings2.cpp:38:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | if (a <= lo + hi >> 1) return query(a, lo, lo + hi >> 1, idx << 1);
| ~~~^~~~
meetings2.cpp:38:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | if (a <= lo + hi >> 1) return query(a, lo, lo + hi >> 1, idx << 1);
| ~~~^~~~
meetings2.cpp:39:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | else return query(a, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
| ~~~^~~~
meetings2.cpp: In member function 'int SEG::find(int, int, int, int)':
meetings2.cpp:47:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | push(1 + (lo + hi >> 1), hi, idx << 1 | 1);
| ~~~^~~~
meetings2.cpp:48:58: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | if (T[idx << 1 | 1] >= x) return find(x, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
| ~~~^~~~
meetings2.cpp:49:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | return find(x, lo, lo + hi >> 1, idx << 1);
| ~~~^~~~
meetings2.cpp: In function 'void dfs2(int, int)':
meetings2.cpp:67:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
67 | if (Chk[cur]) return; Sub[cur] = 1;
| ^~
meetings2.cpp:67:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
67 | if (Chk[cur]) return; Sub[cur] = 1;
| ^~~
meetings2.cpp: In function 'void solve(int)':
meetings2.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
| ~~^~~~~~~~~~~~~
meetings2.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < G[k].size(); i++) V[i] = Sub[G[k][i]];
| ~~^~~~~~~~~~~~~
meetings2.cpp:112:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
| ~~^~~~~~~~~~~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:17:47: warning: iteration 400020 invokes undefined behavior [-Waggressive-loop-optimizations]
17 | for (int i = 0; i < M << 2; i++) L[i] = -2 * INF;
| ~~~~~^~~~~~~~~~
meetings2.cpp:17:27: note: within this loop
17 | for (int i = 0; i < M << 2; i++) L[i] = -2 * INF;
| ~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
13152 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
13152 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
13152 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
