#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, size_t D>
ostream &operator << (ostream &os, array<T, D> v) {
os << "{";
for (int i = 0; i < D; ++i) {
os << (i ? ", " : "") << v[i];
}
return os << "}";
}
void __print() {
cerr << "]\n";
}
template<class T, class... V>
void __print(T t, V... v) {
cerr << t;
if (sizeof...(v)) {
cerr << ", ";
}
__print(v...);
}
#define debug(x...) cerr << "[" << #x << "] = ["; __print(x);
const int N = 1e5 + 5, inf = 1e9 + 7;
using Node = array<array<int, 2>, 2>;
int n;
int tin[N], head[N], pr[N], sz[N], tail[N], state[N];
Node s[4 * N];
array<int, 2> sum[N], up[N];
vector<int> g[N];
Node operator + (const Node <, const Node &rt) {
Node res{array<int, 2>{inf, inf}, array<int, 2>{inf, inf}};
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
if (lt[i][j] != inf) {
for (int k = 0; k < 2; ++k) {
for (int l = 0; l < 2; ++l) {
if (rt[k][l] != inf) {
res[i][l] = min(res[i][l], lt[i][j] + rt[k][l] + (j ^ k));
}
}
}
}
}
}
return res;
}
void bld(int id = 1, int l = 1, int r = n) {
if (l == r) {
s[id] = {array<int, 2>{0, inf}, array<int, 2>{inf, 0}};
return;
}
int md = (l + r) / 2;
bld(id * 2, l, md);
bld(id * 2 + 1, md + 1, r);
s[id] = s[id * 2] + s[id * 2 + 1];
}
void upd(int i, int id = 1, int l = 1, int r = n) {
if (l == r) {
if (state[i] == 1) {
s[id][0] = {inf, inf};
} else {
s[id][0] = {sum[i][0], inf};
}
if (state[i] == 2) {
s[id][1] = {inf, inf};
} else {
s[id][1] = {inf, sum[i][1]};
}
return;
}
int md = (l + r) / 2;
if (i <= md) {
upd(i, id * 2, l, md);
} else {
upd(i, id * 2 + 1, md + 1, r);
}
s[id] = s[id * 2] + s[id * 2 + 1];
}
void dfs(int u) {
for (int &v : g[u]) {
if (v == pr[u]) {
swap(v, g[u].back());
g[u].pop_back();
break;
}
}
sz[u] = 1;
for (int v : g[u]) {
pr[v] = u;
dfs(v);
sz[u] += sz[v];
}
}
int order;
void hld(int u, int h) {
head[u] = h;
tin[u] = tail[h] = ++order;
if (g[u].size()) {
int x = *max_element(g[u].begin(), g[u].end(), [&](int i, int j) {
return sz[i] < sz[j];
});
hld(x, h);
for (int v : g[u]) {
if (v != x) {
hld(v, v);
}
}
}
}
Node qry(int u, int v, int id = 1, int l = 1, int r = n) {
if (u <= l && r <= v) {
return s[id];
}
int md = (l + r) / 2;
if (v <= md) {
return qry(u, v, id * 2, l, md);
}
if (md < u) {
return qry(u, v, id * 2 + 1, md + 1, r);
}
return qry(u, v, id * 2, l, md) + qry(u, v, id * 2 + 1, md + 1, r);
}
int chg(int u, int x) {
state[u] = x;
for (; u; u = pr[head[u]]) {
upd(u);
u = head[u];
int p = pr[u];
auto dat = qry(tin[u], tail[u]);
array<int, 2> c{min(dat[0][0], dat[0][1]), min(dat[1][0], dat[1][1])};
for (auto it : {0, 1}) {
sum[p][it] -= up[u][it];
up[u][it] = min(c[it], c[it ^ 1] + 1);
sum[p][it] += up[u][it];
}
}
int res = inf;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
res = min(res, s[1][i][j]);
}
}
return res;
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for (int i = 0; i < n - 1; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
dfs(1);
hld(1, 1);
}
int cat(int v) {
return chg(v, 2);
}
int dog(int v) {
return chg(v, 1);
}
int neighbor(int v) {
return chg(v, 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
