#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1e9;
int n;
int a[N];
int par[N], nchild[N];
int T, head[N], pos[N], L[N], R[N];
vector<int> G[N];
struct Node {
int f[2][2];
Node() {
f[0][0] = f[1][1] = f[0][1] = f[1][0] = INF;
}
Node operator + (Node x) {
Node ret;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
for (int l = 0; l < 2; ++l) {
ret.f[i][l] = min(ret.f[i][l], f[i][j] + x.f[k][l] + (j ^ k));
}
}
}
}
return ret;
}
};
struct SegmentTree {
vector<Node> T;
#define mid ((l + r) >> 1)
void build(int i, int l, int r) {
if (l == r) {
T[i].f[0][0] = T[i].f[1][1] = 0; return;
}
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
T[i] = T[i << 1] + T[i << 1 | 1];
}
void upd(int i, int l, int r, int p, int v0, int v1) {
if (l == r) {
T[i].f[0][0] += v0, T[i].f[1][1] += v1; return;
}
if (mid >= p) upd(i << 1, l, mid, p, v0, v1);
else upd(i << 1 | 1, mid + 1, r, p, v0, v1);
T[i] = T[i << 1] + T[i << 1 | 1];
}
#undef mid
} IT[N];
void dfs(int u) {
nchild[u] = 1;
for (auto v : G[u]) {
if (v == par[u]) continue;
par[v] = u, dfs(v), nchild[u] += nchild[v];
}
}
void dfsHld(int u) {
if (head[u] == -1) head[u] = u;
pos[u] = ++T;
int nx = -1;
for (auto v : G[u]) {
if (v == par[u]) continue;
if (nx == -1 || nchild[nx] < nchild[v]) nx = v;
}
if (nx != -1) { head[nx] = head[u], dfsHld(nx); }
for (auto v : G[u]) {
if (v == par[u] || v == nx) continue; dfsHld(v);
}
}
void initialize(int _n, vector<int> A, vector<int> B) {
n = _n;
for (int i = 0; i < (n - 1); ++i) {
--A[i], --B[i];
G[A[i]].push_back(B[i]), G[B[i]].push_back(A[i]);
}
memset(head, -1, sizeof head);
dfs(0), dfsHld(0);
for (int i = 0; i < n; ++i) L[i] = n, R[i] = 1;
for (int i = 0; i < n; ++i) {
L[head[i]] = min(L[head[i]], pos[i]);
R[head[i]] = max(R[head[i]], pos[i]);
}
for (int i = 0; i < n; ++i) {
if (head[i] != i) continue;
int tmp = R[i] - L[i] + 1;
IT[i].T.assign(tmp * 4 + 5, Node());
IT[i].build(1, L[i], R[i]);
}
}
void upd(int u, int v0, int v1) {
while (head[u] != head[0]) {
int p = head[u];
int x[2], y[2];
x[0] = x[1] = INF;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
x[i] = min(x[i], IT[p].T[1].f[j][k] + (i ^ j));
}
}
}
IT[p].upd(1, L[p], R[p], pos[u], v0, v1);
y[0] = y[1] = INF;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
y[i] = min(y[i], IT[p].T[1].f[j][k] + (i ^ j));
}
}
}
u = par[p], v0 = y[0] - x[0], v1 = y[1] - x[1];
}
IT[0].upd(1, L[0], R[0], pos[u], v0, v1);
}
int get() {
int ret = INF;
for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) {
ret = min(ret, IT[0].T[1].f[i][j]);
}
return ret;
}
int cat(int v) {
--v, a[v] = 0, upd(v, 0, INF); return get();
}
int dog(int v) {
--v, a[v] = 1, upd(v, INF, 0); return get();
}
int neighbor(int v) {
--v; if (!a[v]) upd(v, 0, -INF); else upd(v, -INF, 0); return get();
}
