#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
const int N = 100100;
const int inf = 1e9;
struct Arr {
array<array<int, 2>, 2> a;
Arr() { a[0][0] = a[0][1] = a[1][0] = a[1][1] = inf; };
array<int, 2>& operator [](int id) { return a[id]; }
};
Arr mrg(Arr x,Arr y) {
Arr z;
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) {
z[i][l] = min(z[i][l], x[i][j] + (j ^ k) + y[k][l]);
}
}
}
}
return z;
}
#define md ((l + r) >> 1)
struct SegTree {
vector<Arr> t;
void resize(int n) {
t.resize((n + 1) << 2);
}
void build(int v,int l,int r) {
if (l == r) {
t[v][0][0] = t[v][1][1] = 0;
return;
}
build(v << 1, l, md);
build(v << 1 | 1, md + 1, r);
t[v] = mrg(t[v << 1], t[v << 1 | 1]);
}
void add(int v,int l,int r,int p,int v0,int v1) {
if (p < l || p > r) return;
if (l == r) {
t[v][0][0] += v0;
t[v][1][1] += v1;
return;
}
add(v << 1, l, md, p, v0, v1);
add(v << 1 | 1, md + 1, r, p, v0, v1);
t[v] = mrg(t[v << 1], t[v << 1 | 1]);
}
} t[N];
int a[N];
vector<int> g[N];
int child[N];
int up[N], par[N];
int tin[N], tt;
int ll[N], rr[N];
void dfs(int u) {
child[u] = 1;
for (int v : g[u]) {
if (v != par[u]) {
par[v] = u;
dfs(v);
child[u] += child[v];
}
}
}
void hld(int u,int root) {
up[u] = root;
tin[u] = ++tt;
int nxt = 0;
for (int v : g[u]) {
if (v != par[u]) {
if (child[v] > child[nxt]) {
nxt = v;
}
}
}
if (nxt) {
hld(nxt, root);
}
for (int v : g[u]) {
if (v != par[u] && v != nxt) {
hld(v, v);
}
}
}
void initialize(int n, vector<int> a,vector<int> b) {
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);
for (int i = 1; i <= n; ++i) ll[i] = n, rr[i] = 1;
for (int i = 1; i <= n; ++i) {
ll[up[i]] = min(ll[up[i]], tin[i]);
rr[up[i]] = max(rr[up[i]], tin[i]);
}
for (int i = 1; i <= n; ++i) {
if (up[i] == i) {
t[i].resize(rr[i] - ll[i] + 1);
t[i].build(1, ll[i], rr[i]);
}
}
}
void add(int u,int v0,int v1) {
while (up[u] != up[1]) {
int v = up[u];
int nw[2], nx[2];
nw[0] = nw[1] = inf;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
nw[i] = min(nw[i], (i ^ j) + t[v].t[1][j][k]);
}
}
}
t[v].add(1, ll[v], rr[v], tin[u], v0, v1);
nx[0] = nx[1] = inf;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
nx[i] = min(nx[i], (i ^ j) + t[v].t[1][j][k]);
}
}
}
u = par[v], v0 = nx[0] - nw[0], v1 = nx[1] - nw[1];
}
t[1].add(1, ll[1], rr[1], tin[u], v0, v1);
}
int go() {
int ans = inf;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
ans = min(ans, t[1].t[1][i][j]);
}
}
return ans;
}
int cat(int u) {
a[u] = 0; add(u, 0, inf); return go();
}
int dog(int u) {
a[u] = 1; add(u, inf, 0); return go();
}
int neighbor(int u) {
if (a[u]) add(u, -inf, 0);
else add(u, 0, -inf);
return go();
}
