#include "catdog.h"
#include <bits/stdc++.h>
const int N = 1e5 + 50;
int n, fa[N], top[N], dep[N], g[N][2], siz[N], son[N], dfn[N], dp[N][2], tot, tail[N], delta[N][2], id[N];
std::vector<int> G[N];
inline int lc(int o) { return o << 1; }
inline int rc(int o) { return o << 1 | 1; }
struct matrix_t {
int M[2][2], n, m;
matrix_t(int n = 0, int m = 0) : n(n), m(m) {
memset(M, 0x3f, sizeof M);
}
void set(int g0, int g1) {
M[0][0] = g0, M[1][0] = g0 + 1;
M[0][1] = g1 + 1, M[1][1] = g1;
}
} gm[N], tr[N << 2];
matrix_t operator*(const matrix_t &lhs, const matrix_t &rhs) {
matrix_t res;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k)
res.M[i][j] = std::min(res.M[i][j], lhs.M[i][k] + rhs.M[k][j]);
return res;
}
void dfs(int x, int f, int d) {
fa[x] = f, dep[x] = d, siz[x] = 1;
int mx = -1;
dp[x][0] = dp[x][1] = 0;
for (int y : G[x])
if (y != f) {
dfs(y, x, d + 1);
siz[x] += siz[y];
if (siz[y] > mx) {
mx = siz[y];
son[x] = y;
}
dp[x][0] = std::min(dp[y][0], dp[y][1] + 1);
dp[x][1] = std::min(dp[y][1], dp[y][0] + 1);
}
}
void dfs2(int x, int topf) {
dfn[x] = ++tot;
id[tot] = x;
top[x] = topf;
tail[topf] = x;
g[x][0] = g[x][1] = 0;
if (son[x]) {
dfs2(son[x], topf);
for (int y : G[x])
if (y != fa[x] && y != son[x]) {
dfs2(y, y);
g[x][0] += std::min(dp[y][0], dp[y][1] + 1);
g[x][1] += std::min(dp[y][1], dp[y][0] + 1);
}
}
gm[x].set(g[x][0], g[x][1]);
}
void push_up(int o) {
tr[o] = tr[rc(o)] * tr[lc(o)];
}
void build(int o, int l, int r) {
if (l == r) {
tr[o] = gm[id[l]];
}
else {
const int mid = l + r >> 1;
build(lc(o), l, mid);
build(rc(o), mid + 1, r);
push_up(o);
}
}
matrix_t query(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return tr[o];
const int mid = l + r >> 1;
if (qr <= mid) return query(lc(o), l, mid, ql, qr);
if (ql > mid) return query(rc(o), mid + 1, r, ql, qr);
return query(rc(o), mid + 1, r, ql, qr) * query(lc(o), l, mid, ql, qr);
}
void modify(int o, int l, int r, int p) {
if (l == r) {
tr[o] = gm[id[l]];
}
else {
const int mid = l + r >> 1;
if (p <= mid) modify(lc(o), l, mid, p);
else modify(rc(o), mid + 1, r, p);
push_up(o);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for (int i = 0; i < A.size(); ++i) {
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
dfs(1, 0, 1);
dfs2(1, 1);
assert(tot == N);
build(1, 1, N);
}
void cancel(int v) {
g[v][0] -= delta[v][0];
g[v][1] -= delta[v][1];
}
void update(int v) {
g[v][0] += delta[v][0];
g[v][1] += delta[v][1];
gm[v].set(g[v][0], g[v][1]);
}
void travel(int x) {
while (x) {
matrix_t old = query(1, 1, n, dfn[top[x]], dfn[tail[top[x]]]);
modify(1, 1, n, dfn[x]);
matrix_t now = query(1, 1, n, dfn[top[x]], dfn[tail[top[x]]]);
x = fa[top[x]];
if (!x) break;
{
int f0 = std::min(old.M[0][0], old.M[1][0]);
int f1 = std::min(old.M[0][1], old.M[1][1]);
g[x][0] -= std::min(f0, f1 + 1);
g[x][1] -= std::min(f1, f0 + 1);
}
{
int f0 = std::min(now.M[0][0], now.M[1][0]);
int f1 = std::min(now.M[0][1], now.M[1][1]);
g[x][0] += std::min(f0, f1 + 1);
g[x][1] += std::min(f1, f0 + 1);
}
gm[x].set(g[x][0], g[x][1]);
}
}
int getans() {
auto M = query(1, 1, n, dfn[1], dfn[tail[top[1]]]);
int ans = std::min(M.M[0][0], M.M[0][1]);
ans = std::min(ans, M.M[1][0]);
ans = std::min(ans, M.M[1][1]);
return ans;
}
int cat(int v) {
cancel(v);
delta[v][0] = 0, delta[v][1] = 0x3f3f3f3f;
update(v);
travel(v);
return getans();
}
int dog(int v) {
cancel(v);
delta[v][0] = 0x3f3f3f3f, delta[v][1] = 0;
update(v);
travel(v);
return getans();
}
int neighbor(int v) {
cancel(v);
delta[v][0] = delta[v][1] = 0;
update(v);
travel(v);
return getans();
}
