#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 5, INF = 1e9;
vector<int> adj[MAXN];
int sz[MAXN], head[MAXN], heavy[MAXN], fa[MAXN], pos[MAXN], pet[MAXN], len[MAXN];
struct Node {
int b[2][2];
Node()
{
b[0][0] = b[1][1] = 0;
b[0][1] = b[1][0] = INF;
}
};
Node Merge(Node const& a, Node const& b)
{
Node res;
res.b[0][0] = res.b[1][0] = res.b[0][1] = res.b[1][1] = INF;
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++)
res.b[i][l] = min(res.b[i][l], a.b[i][j] + b.b[k][l] + (j ^ k));
return res;
}
struct SegTree {
vector<Node> tree;
void Init(int N)
{
tree.resize(N * 4);
}
void Update(int id, int l, int r, int p, int cat, int dog)
{
if (p < l || r < p) return;
if (l == r)
{
tree[id].b[0][0] += cat;
tree[id].b[1][1] += dog;
return;
}
int mid = (l + r) >> 1;
if (p <= mid)
Update(id << 1, l, mid, p, cat, dog);
else
Update(id << 1 | 1, mid + 1, r, p, cat, dog);
tree[id] = Merge(tree[id << 1], tree[id << 1 | 1]);
}
pair<int, int> Get()
{
Node ans = tree[1];
int blocked_if_cat = min({ans.b[0][0], ans.b[0][1], ans.b[1][0] + 1, ans.b[1][1] + 1});
int blocked_if_dog = min({ans.b[1][0], ans.b[1][1], ans.b[0][0] + 1, ans.b[0][1] + 1});
return {blocked_if_cat, blocked_if_dog};
}
} st[MAXN];
void Dfs(int u, int father)
{
sz[u] = 1;
for (int v : adj[u])
if (v != father)
{
fa[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 hd)
{
head[u] = hd;
pos[u] = ++len[hd];
if (heavy[u])
Build(heavy[u], hd);
for (int v : adj[u])
if (v != fa[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++)
{
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
Dfs(1, 0);
Build(1, 1);
for (int i = 1; i <= N; i++)
if (head[i] == i)
st[head[i]].Init(len[head[i]]);
}
void UpdateChains(int u, int cat, int dog)
{
while (u)
{
auto [c0, d0] = st[head[u]].Get();
st[head[u]].Update(1, 1, len[head[u]], pos[u], cat, dog);
auto [c1, d1] = st[head[u]].Get();
cat = c1 - c0;
dog = d1 - d0;
u = fa[head[u]];
}
}
enum {gol, pisica, caine};
int cat(int v)
{
pet[v] = pisica;
UpdateChains(v, 0, INF);
Node res = st[1].tree[1];
return min({res.b[0][0], res.b[0][1], res.b[1][0], res.b[1][1]});
}
int dog(int v)
{
pet[v] = caine;
UpdateChains(v, INF, 0);
Node res = st[1].tree[1];
return min({res.b[0][0], res.b[0][1], res.b[1][0], res.b[1][1]});
}
int neighbor(int v)
{
if (pet[v] == pisica)
UpdateChains(v, 0, -INF);
else
UpdateChains(v, -INF, 0);
pet[v] = gol;
Node res = st[1].tree[1];
return min({res.b[0][0], res.b[0][1], res.b[1][0], res.b[1][1]});
}
