#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 << 2], L[M << 2];
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, 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, 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);
}
} 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, int k) {
for (int x : G[cur]) if (p != x && !Chk[x]) {
dp(cur, x, k);
}
int lo = 1, hi = Sub[cur];
while (lo < hi) {
int m = lo + hi + 1 >> 1;
if (S.query(m) == -INF) hi = m - 1;
else lo = m;
}
if (S.query(lo) == -INF) return;
int t = lo, u = S.query(t); lo = 1; hi = t + 1;
while (lo < hi) {
int m = lo + hi >> 1;
if (Ans.query(m) >= Dep[cur] + u) lo = m + 1;
else hi = m;
}
Ans.update(lo, t, Dep[cur] + u);
}
void update(int p, int cur) {
int lo = 1, hi = Sub[cur] + 1;
while (lo < hi) {
int m = lo + hi >> 1;
if (S.query(m) < Dep[cur]) hi = m;
else lo = m + 1;
}
S.update(lo, 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;
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 lo = 1, hi = n - Sub[x];
while (lo < hi) {
int m = lo + hi >> 1;
if (S.query(m) != -INF) lo = m + 1;
else hi = m;
}
S.update(lo, n - Sub[x], 0);
dp(k, x, Sub[x]); update(k, x);
lo = 1, hi = n - Sub[x];
while (lo < hi) {
int m = lo + hi >> 1;
if (S.query(m) != 0) lo = m + 1;
else hi = m;
}
S.update(lo, n - Sub[x], -INF);
}
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 function 'void dfs2(int, int)':
meetings2.cpp:57:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
57 | if (Chk[cur]) return; Sub[cur] = 1;
| ^~
meetings2.cpp:57:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
57 | if (Chk[cur]) return; Sub[cur] = 1;
| ^~~
meetings2.cpp: In function 'void dp(int, int, int)':
meetings2.cpp:69:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int m = lo + hi + 1 >> 1;
| ~~~~~~~~^~~
meetings2.cpp:76:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int m = lo + hi >> 1;
| ~~~^~~~
meetings2.cpp: In function 'void update(int, int)':
meetings2.cpp:85:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int m = lo + hi >> 1;
| ~~~^~~~
meetings2.cpp: In function 'void solve(int)':
meetings2.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
| ~~^~~~~~~~~~~~~
meetings2.cpp:103:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
103 | int m = lo + hi >> 1;
| ~~~^~~~
meetings2.cpp:111:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
111 | int m = lo + hi >> 1;
| ~~~^~~~
meetings2.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (int i = 0; i < G[k].size(); i++) V[i] = Sub[G[k][i]];
| ~~^~~~~~~~~~~~~
meetings2.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8164 KB |
Output is correct |
| 5 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
8140 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8164 KB |
Output is correct |
| 5 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
8140 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8164 KB |
Output is correct |
| 5 |
Correct |
5 ms |
8140 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
8140 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
