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;
const int maxn = 200010;
int n, tot, sz[maxn], ans[maxn], fa[maxn], rt[maxn], dep[maxn];
vector<int> G[maxn];
struct node {
int l, r, tag, val, ans, mx;
node() { tag = val = ans = mx = -1000000; }
} t[maxn * 40];
#define mid (l + r >> 1)
void maintain(int k) {
t[k].mx = max(t[t[k].l].mx, t[t[k].r].mx);
}
void pushdown(int k) {
if (t[k].tag == -1000000) return;
int ls = t[k].l, rs = t[k].r;
if (ls) {
t[ls].tag = max(t[ls].tag, t[k].tag);
t[ls].ans = max(t[ls].ans, t[ls].val + t[ls].tag);
}
if (rs) {
t[rs].tag = max(t[rs].tag, t[k].tag);
t[rs].ans = max(t[rs].ans, t[rs].val + t[rs].tag);
}
t[k].tag = -1000000;
}
void modify1(int &k, int l, int r, int p, int v) {
if (!k) k = ++tot;
if (l == r) {
t[k].mx = t[k].val = max(t[k].mx, v);
t[k].tag = -1000000; return;
}
pushdown(k);
if (mid >= p) modify1(t[k].l, l, mid, p, v);
else modify1(t[k].r, mid + 1, r, p, v);
maintain(k);
}
void modify2(int &k, int l, int r, int p, int v) {
if (!k) k = ++tot;
if (l == r) { t[k].ans = max(t[k].ans, v); return; }
pushdown(k);
if (mid >= p) modify2(t[k].l, l, mid, p, v);
else modify2(t[k].r, mid + 1, r, p, v);
maintain(k);
}
int qmax(int k, int l, int r, int ql, int qr) {
if (!k || l >= ql && r <= qr) return t[k].mx;
pushdown(k);
int ans = -1000000;
if (mid >= ql) ans = qmax(t[k].l, l, mid, ql, qr);
if (mid < qr) ans = max(ans, qmax(t[k].r, mid + 1, r, ql, qr));
return ans;
}
void update(int k, int l, int r, int ql, int qr, int v) {
if (!k) return;
if (l >= ql && r <= qr) {
t[k].tag = max(t[k].tag, v);
t[k].ans = max(t[k].ans, t[k].val + t[k].tag); return;
}
pushdown(k);
if (mid >= ql) update(t[k].l, l, mid, ql, qr, v);
if (mid < qr) update(t[k].r, mid + 1, r, ql, qr, v);
maintain(k);
}
int merge(int k1, int k2, int l, int r, int mx1, int mx2, int val) {
if (!k1 && !k2) return 0;
if (!k2) {
t[k1].tag = max(t[k1].tag, mx2 + val);
t[k1].ans = max(t[k1].ans, t[k1].val + t[k1].tag);
return k1;
}
if (!k1) {
t[k2].tag = max(t[k2].tag, mx1 + val);
t[k2].ans = max(t[k2].ans, t[k2].val + t[k2].tag);
return k2;
}
if (l == r) {
t[k1].ans = max({t[k1].ans, t[k2].ans, t[k1].val + max(mx2, t[k2].val)
+ val, t[k2].val + max(mx1, t[k1].val) + val});
t[k1].val = t[k1].mx = max(t[k1].val, t[k2].val);
t[k1].tag = -1000000; return k1;
}
pushdown(k1), pushdown(k2);
t[k1].l = merge(t[k1].l, t[k2].l, l, mid, max(mx1, t[t[k1].r].mx), max(mx2,
t[t[k2].r].mx), val);
t[k1].r = merge(t[k1].r, t[k2].r, mid + 1, r, mx1, mx2, val);
maintain(k1); return k1;
}
void dfs(int k, int l, int r) {
if (!k) return;
if (l == r) { ans[l] = max(ans[l], t[k].ans + 1); return; }
pushdown(k);
dfs(t[k].l, l, mid), dfs(t[k].r, mid + 1, r);
}
int main() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
function<void(int)> dfs1 = [&](int v) {
sz[v] = 1;
for (int u : G[v]) if (u ^ fa[v]) {
dep[u] = dep[v] + 1;
fa[u] = v, dfs1(u), sz[v] += sz[u];
}
};
function<void(int)> dfs2 = [&](int v) {
for (int u : G[v]) if (u ^ fa[v]) {
dfs2(u);
rt[v] = merge(rt[v], rt[u], 1, n, -1000000, -1000000, -2 * dep[v]);
}
modify1(rt[v], 1, n, sz[v], dep[v]);
if (v > 1) {
int t = n - sz[v];
update(rt[v], 1, n, 1, t, -dep[fa[v]]);
modify2(rt[v], 1, n, t, qmax(rt[v], 1, n, t, n) - dep[fa[v]]);
}
};
dfs1(1), dfs2(1), dfs(rt[1], 1, n);
for (int i = n - 1; i; i--) {
ans[i] = max(ans[i], ans[i + 1]);
}
for (int i = 1; i <= n; i++) {
if (i & 1) puts("1");
else printf("%d\n", max(1, ans[i >> 1]));
}
return 0;
}
Compilation message (stderr)
meetings2.cpp: In function 'void modify1(int&, int, int, int, int)':
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:38:6: note: in expansion of macro 'mid'
38 | if (mid >= p) modify1(t[k].l, l, mid, p, v);
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:38:35: note: in expansion of macro 'mid'
38 | if (mid >= p) modify1(t[k].l, l, mid, p, v);
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:39:23: note: in expansion of macro 'mid'
39 | else modify1(t[k].r, mid + 1, r, p, v);
| ^~~
meetings2.cpp: In function 'void modify2(int&, int, int, int, int)':
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:47:6: note: in expansion of macro 'mid'
47 | if (mid >= p) modify2(t[k].l, l, mid, p, v);
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:47:35: note: in expansion of macro 'mid'
47 | if (mid >= p) modify2(t[k].l, l, mid, p, v);
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:48:23: note: in expansion of macro 'mid'
48 | else modify2(t[k].r, mid + 1, r, p, v);
| ^~~
meetings2.cpp: In function 'int qmax(int, int, int, int, int)':
meetings2.cpp:53:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
53 | if (!k || l >= ql && r <= qr) return t[k].mx;
| ~~~~~~~~^~~~~~~~~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:56:6: note: in expansion of macro 'mid'
56 | if (mid >= ql) ans = qmax(t[k].l, l, mid, ql, qr);
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:56:39: note: in expansion of macro 'mid'
56 | if (mid >= ql) ans = qmax(t[k].l, l, mid, ql, qr);
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:57:6: note: in expansion of macro 'mid'
57 | if (mid < qr) ans = max(ans, qmax(t[k].r, mid + 1, r, ql, qr));
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:57:44: note: in expansion of macro 'mid'
57 | if (mid < qr) ans = max(ans, qmax(t[k].r, mid + 1, r, ql, qr));
| ^~~
meetings2.cpp: In function 'void update(int, int, int, int, int, int)':
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:68:6: note: in expansion of macro 'mid'
68 | if (mid >= ql) update(t[k].l, l, mid, ql, qr, v);
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:68:35: note: in expansion of macro 'mid'
68 | if (mid >= ql) update(t[k].l, l, mid, ql, qr, v);
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:69:6: note: in expansion of macro 'mid'
69 | if (mid < qr) update(t[k].r, mid + 1, r, ql, qr, v);
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:69:31: note: in expansion of macro 'mid'
69 | if (mid < qr) update(t[k].r, mid + 1, r, ql, qr, v);
| ^~~
meetings2.cpp: In function 'int merge(int, int, int, int, int, int, int)':
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:92:39: note: in expansion of macro 'mid'
92 | t[k1].l = merge(t[k1].l, t[k2].l, l, mid, max(mx1, t[t[k1].r].mx), max(mx2,
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:94:36: note: in expansion of macro 'mid'
94 | t[k1].r = merge(t[k1].r, t[k2].r, mid + 1, r, mx1, mx2, val);
| ^~~
meetings2.cpp: In function 'void dfs(int, int, int)':
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:102:17: note: in expansion of macro 'mid'
102 | dfs(t[k].l, l, mid), dfs(t[k].r, mid + 1, r);
| ^~~
meetings2.cpp:12:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | #define mid (l + r >> 1)
| ~~^~~
meetings2.cpp:102:35: note: in expansion of macro 'mid'
102 | dfs(t[k].l, l, mid), dfs(t[k].r, mid + 1, r);
| ^~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
meetings2.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
