#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 5;
vector<int> g[MAXN];
const int INF = 1e9;
int sz[MAXN], head[MAXN], heavy[MAXN], par[MAXN], in[MAXN], val[MAXN];
/// 0: cat, 1: dog
struct Node {
int dp[2][2];
Node() {
dp[0][0] = dp[1][1] = 0;
dp[0][1] = dp[1][0] = INF;
}
};
Node comb(Node a, Node b) {
Node res; res.dp[0][0] = res.dp[1][0] = res.dp[0][1] = res.dp[1][1] = INF;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
if (a.dp[i][j] < INF) {
for (int u = 0; u < 2; u++) {
for (int v = 0; v < 2; v++) {
if (b.dp[u][v] < INF) {
res.dp[i][v] = min(res.dp[i][v], a.dp[i][j] + b.dp[u][v] + (j ^ u));
}
}
}
}
}
}
return res;
}
struct SegTree {
vector<Node> tree;
void init(int N) {
tree.resize(N * 4);
}
void update(int n, int p, int cat, int dog) {
int l = 1, r = n, id = 1;
while (l < r) {
int mid = (l + r) >> 1;
if (p <= mid) id = id << 1, r = mid;
else id = id << 1 | 1, l = mid + 1;
}
tree[id].dp[0][0] += cat;
tree[id].dp[1][1] += dog;
while (id) {
id >>= 1;
tree[id] = comb(tree[id << 1], tree[id << 1 | 1]);
}
}
pair<int, int> get(void) {
Node ans = tree[1];
int cat = min({ans.dp[0][0], ans.dp[0][1], ans.dp[1][0] + 1, ans.dp[1][1] + 1});
int dog = min({ans.dp[1][0], ans.dp[1][1], ans.dp[0][0] + 1, ans.dp[0][1] + 1});
return {cat, dog};
}
} st[MAXN];
void dfs(int u, int p) {
sz[u] = 1;
for (int v : g[u]) {
if (v != p) {
par[v] = u;
dfs(v, u);
sz[u] += sz[v];
if (heavy[u] == 0 || sz[v] > sz[heavy[u]]) heavy[u] = v;
}
}
}
void build(int u, int h) {
head[u] = h;
in[u] = ++sz[h];
if (heavy[u]) build(heavy[u], h);
for (int v : g[u]) {
if (v != par[u] && v != heavy[u]) {
build(v, v);
}
}
}
void initialize(int N, vector<int> A, vector<int> B) {
for (int i = 0; i < N - 1; i++) {
g[A[i]].emplace_back(B[i]);
g[B[i]].emplace_back(A[i]);
}
dfs(1, 0);
for (int i = 1; i <= N; i++) sz[i] = 0;
build(1, 1);
for (int i = 1; i <= N; i++) if (head[i] == i) {
st[head[i]].init(sz[head[i]]);
}
}
void upd(int u, int cat, int dog) {
while (u) {
auto lst = st[head[u]].get();
st[head[u]].update(sz[head[u]], in[u], cat, dog);
auto cur = st[head[u]].get();
cat = cur.first - lst.first;
dog = cur.second - lst.second;
u = par[head[u]];
}
}
int cat(int v) {
val[v] = 1;
upd(v, 0, INF);
Node res = st[1].tree[1];
return min({res.dp[0][0], res.dp[0][1], res.dp[1][0], res.dp[1][1]});
}
int dog(int v) {
val[v] = 2;
upd(v, INF, 0);
Node res = st[1].tree[1];
return min({res.dp[0][0], res.dp[0][1], res.dp[1][0], res.dp[1][1]});
}
int neighbor(int v) {
if (val[v] == 1) {
upd(v, 0, -INF);
} else {
upd(v, -INF, 0);
}
val[v] = 0;
Node res = st[1].tree[1];
return min({res.dp[0][0], res.dp[0][1], res.dp[1][0], res.dp[1][1]});
}
