#include <bits/stdc++.h>
using namespace std;
template <class X, class Y>
bool cmin(X &a, const Y &b) {
return a > b ? a = b, 1 : 0;
}
const int INF = 1e9;
struct segTree {
using Tp = array <array <int, 2>, 2>;
vector <Tp> tr; int n, lo, hi; Tp res;
Tp base() {
Tp c; c[0][1] = c[1][0] = INF;
c[0][0] = c[1][1] = 0; return c;
}
Tp comb(const Tp &a, const Tp &b) {
if (a[0][0] < 0) return b; Tp c;
c[0][1] = min({a[0][0] +
b[0][1], a[0][0] + b[1][1]
+ 1, a[0][1] + b[1][1],
a[0][1] + b[0][1] + 1, INF});
c[1][0] = min({a[1][0] +
b[0][0], a[1][0] + b[1][0]
+ 1, a[1][1] + b[1][0],
a[1][1] + b[0][0] + 1, INF});
c[0][0] = min({a[0][0] +
b[0][0], a[0][0] + b[1][0]
+ 1, a[0][1] + b[1][0],
a[0][1] + b[0][0] + 1, INF});
c[1][1] = min({a[1][0] +
b[0][1], a[1][0] + b[1][1]
+ 1, a[1][1] + b[1][1],
a[1][1] + b[0][1] + 1, INF});
return c;
}
void build(int i, int l, int r) {
if (l == r) tr[i] = base();
else {
int m = (l + r) / 2;
build(i * 2, l, m);
build(i * 2 + 1, m + 1, r);
tr[i][0][1] = min({INF,
tr[i * 2][0][0] + tr[i * 2 + 1][0][1],
tr[i * 2][0][0] + tr[i * 2 + 1][1][1] + 1,
tr[i * 2][0][1] + tr[i * 2 + 1][1][1],
tr[i * 2][0][1] + tr[i * 2 + 1][0][1] + 1});
tr[i][1][0] = min({INF,
tr[i * 2][1][0] + tr[i * 2 + 1][0][0],
tr[i * 2][1][0] + tr[i * 2 + 1][1][0] + 1,
tr[i * 2][1][1] + tr[i * 2 + 1][1][0],
tr[i * 2][1][1] + tr[i * 2 + 1][0][0] + 1});
tr[i][0][0] = min({INF,
tr[i * 2][0][0] + tr[i * 2 + 1][0][0],
tr[i * 2][0][0] + tr[i * 2 + 1][1][0]
+ 1, tr[i * 2][0][1] + tr[i * 2 + 1][1][0],
tr[i * 2][0][1] + tr[i * 2 + 1][0][0] + 1});
tr[i][1][1] = min({INF,
tr[i * 2][1][0] + tr[i * 2 + 1][0][1],
tr[i * 2][1][0] + tr[i * 2 + 1][1][1] + 1,
tr[i * 2][1][1] + tr[i * 2 + 1][1][1],
tr[i * 2][1][1] + tr[i * 2 + 1][0][1] + 1,});
}
}
void init(int n) {
tr.resize((this->n = n) * 4);
build(1, 1, n);
}
void update(int i, int l, int r, int t, int v) {
if (l == r) return void(tr[i][t][t] = v);
int m = (l + r) / 2;
if (m >= lo) update(i * 2, l, m, t, v);
else update(i * 2 + 1, m + 1, r, t, v);
tr[i][0][1] = min({INF,
tr[i * 2][0][0] + tr[i * 2 + 1][0][1],
tr[i * 2][0][0] + tr[i * 2 + 1][1][1] + 1,
tr[i * 2][0][1] + tr[i * 2 + 1][1][1],
tr[i * 2][0][1] + tr[i * 2 + 1][0][1] + 1});
tr[i][1][0] = min({INF,
tr[i * 2][1][0] + tr[i * 2 + 1][0][0],
tr[i * 2][1][0] + tr[i * 2 + 1][1][0] + 1,
tr[i * 2][1][1] + tr[i * 2 + 1][1][0],
tr[i * 2][1][1] + tr[i * 2 + 1][0][0] + 1});
tr[i][0][0] = min({INF,
tr[i * 2][0][0] + tr[i * 2 + 1][0][0],
tr[i * 2][0][0] + tr[i * 2 + 1][1][0]
+ 1, tr[i * 2][0][1] + tr[i * 2 + 1][1][0],
tr[i * 2][0][1] + tr[i * 2 + 1][0][0] + 1});
tr[i][1][1] = min({INF,
tr[i * 2][1][0] + tr[i * 2 + 1][0][1],
tr[i * 2][1][0] + tr[i * 2 + 1][1][1] + 1,
tr[i * 2][1][1] + tr[i * 2 + 1][1][1],
tr[i * 2][1][1] + tr[i * 2 + 1][0][1] + 1,});
}
void update(int p, int t, int v) {
lo = p; update(1, 1, n, t, v);
}
void query(int i, int l, int r) {
if (l >= lo && r <= hi) {
if (res[0][0] < 0) res = tr[i];
else {
Tp tmp;
tmp[0][1] = min({res[0][0] +
b[0][1], res[0][0] + tr[i][1][1]
+ 1, res[0][1] + tr[i][1][1],
res[0][1] + tr[i][0][1] + 1, INF});
tmp[1][0] = min({res[1][0] +
tr[i][0][0], res[1][0] + tr[i][1][0]
+ 1, res[1][1] + tr[i][1][0],
res[1][1] + tr[i][0][0] + 1, INF});
tmp[0][0] = min({res[0][0] +
tr[i][0][0], res[0][0] + tr[i][1][0]
+ 1, res[0][1] + tr[i][1][0],
res[0][1] + tr[i][0][0] + 1, INF});
tmp[1][1] = min({res[1][0] +
tr[i][0][1], res[1][0] + tr[i][1][1]
+ 1, res[1][1] + tr[i][1][1],
res[1][1] + tr[i][0][1] + 1, INF});
res = tmp;
}
return;
}
int m = (l + r) / 2;
if (m >= lo) query(i * 2, l, m);
if (m < hi) query(i * 2 + 1, m + 1, r);
}
Tp query(int l, int r) {
lo = l; hi = r; res[0][0] = -1;
query(1, 1, n); return res;
}
};
const int N = 100005;
vector <int> adj[N];
int f[N][2], g[N][2];
int hv[N], head[N], par[N], col[N];
int tin[N], tout[N], timer, en[N];
segTree ST;
int DFSpre(int u) {
int sz = 1, big = 0, tmp;
for (int v : adj[u]) {
if (v == par[u]) continue;
par[v] = u;
sz += tmp = DFSpre(v);
if (tmp > big) {
tmp = big; hv[u] = v;
}
}
return sz;
}
void DFSsplit(int u) {
tin[u] = ++timer;
if (par[u] && u == hv[par[u]])
head[u] = head[par[u]];
else head[u] = u;
if (hv[u]) {
DFSsplit(hv[u]); en[u] = en[hv[u]];
}
else en[u] = u;
for (int v : adj[u])
if (v != par[u] && v != hv[u])
DFSsplit(v);
tout[u] = timer;
}
void update(int u, int t) {
if (t < 2) ST.update(tin[u], 1 - t, INF);
else ST.update(tin[u], 1 - col[u], g[u][1 - col[u]]);
col[u] = t;
while (u) {
u = head[u];
if (par[u]) {
g[par[u]][0] -= min(f[u][0], f[u][1] + 1);
g[par[u]][1] -= min(f[u][0] + 1, f[u][1]);
}
auto res = ST.query(tin[u], tin[en[u]]);
if (col[u] == 0 || col[u] == 2)
f[u][0] = min(res[0][0], res[0][1]);
else f[u][0] = INF;
if (col[u] == 1 || col[u] == 2)
f[u][1] = min(res[1][0], res[1][1]);
else f[u][1] = INF;
if (par[u]) {
g[par[u]][0] += min(f[u][0], f[u][1] + 1);
if (col[par[u]] == 0 || col[par[u]] == 2)
ST.update(tin[par[u]], 0, g[par[u]][0]);
g[par[u]][1] += min(f[u][0] + 1, f[u][1]);
if (col[par[u]] == 1 || col[par[u]] == 2)
ST.update(tin[par[u]], 1, g[par[u]][1]);
}
u = par[u];
}
}
void initialize(int n, vector <int> a, vector <int> b) {
fill(col + 1, col + n + 1, 2);
for (int i = 0; i < n - 1; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
DFSpre(1); DFSsplit(1); ST.init(n);
}
int cat(int u) {
update(u, 0); return min(f[1][0], f[1][1]);
}
int dog(int u) {
update(u, 1); return min(f[1][0], f[1][1]);
}
int neighbor(int u) {
update(u, 2); return min(f[1][0], f[1][1]);
}
Compilation message
catdog.cpp: In member function 'segTree::Tp segTree::comb(const Tp&, const Tp&)':
catdog.cpp:23:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
23 | if (a[0][0] < 0) return b; Tp c;
| ^~
catdog.cpp:23:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
23 | if (a[0][0] < 0) return b; Tp c;
| ^~
catdog.cpp: In member function 'void segTree::query(int, int, int)':
catdog.cpp:114:17: error: 'b' was not declared in this scope
114 | b[0][1], res[0][0] + tr[i][1][1]
| ^
catdog.cpp:116:50: error: no matching function for call to 'min(<brace-enclosed initializer list>)'
116 | res[0][1] + tr[i][0][1] + 1, INF});
| ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from catdog.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
198 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: template argument deduction/substitution failed:
catdog.cpp:116:50: note: candidate expects 2 arguments, 1 provided
116 | res[0][1] + tr[i][0][1] + 1, INF});
| ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from catdog.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
246 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: template argument deduction/substitution failed:
catdog.cpp:116:50: note: candidate expects 3 arguments, 1 provided
116 | res[0][1] + tr[i][0][1] + 1, INF});
| ^
In file included from /usr/include/c++/9/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from catdog.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3444 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3450 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: template argument deduction/substitution failed:
