#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
struct segtree {
segtree *left, *right;
array<long long, 4> mini;
void pull() {
mini = {N, N, N, N};
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
int k = i / 2 * 2 + j % 2;
mini[k] = min(mini[k], left->mini[i] + right->mini[j] + (i % 2 != j / 2));
}
}
}
segtree(int l, int r) {
if (l == r) {
mini = {0, N, N, 0};
} else {
int m = (l + r) / 2;
left = new segtree(l, m);
right = new segtree(m + 1, r);
pull();
}
}
void update(int a, long long x, long long y, int l, int r) {
if (l == r) {
mini[0] += x;
mini[3] += y;
} else {
int m = (l + r) / 2;
if (a <= m) {
left->update(a, x, y, l, m);
} else {
right->update(a, x, y, m + 1, r);
}
pull();
}
}
};
int par[N], sub[N], in[N], head[N], tail[N];
segtree *path[N];
vector<int> adj[N];
int type[N];
void dfs_sub(int u) {
sub[u] = 1;
for (auto &c : adj[u]) {
adj[c].erase(find(adj[c].begin(), adj[c].end(), u));
par[c] = u;
dfs_sub(c);
sub[u] += sub[c];
if (sub[c] > sub[adj[u][0]]) {
swap(adj[u][0], c);
}
}
}
void dfs_hld(int u) {
sub[u] = 0;
for (auto c : adj[u]) {
if (c == adj[u][0]) {
head[c] = head[u];
in[c] = in[u] + 1;
} else {
head[c] = c;
}
dfs_hld(c);
}
++sub[head[u]];
}
array<long long, 2> get(array<long long, 4> &a) {
long long x = min(a[0], a[1]), y = min(a[2], a[3]);
return {min(x, y + 1), min(x + 1, y)};
}
void dfs_build(int u) {
if (head[u] == u) {
path[u] = new segtree(0, sub[u] - 1);
}
for (auto c : adj[u]) {
dfs_build(c);
}
if (head[u] == u && u > 1) {
array<long long, 2> mini = get(path[u]->mini);
int p = par[u], v = head[p];
path[v]->update(in[p], mini[0], mini[1], 0, sub[v] - 1);
}
}
void update(int u, long long x, long long y) {
while (u > 0) {
int v = head[u];
array<long long, 2> prv = get(path[v]->mini);
path[v]->update(in[u], x, y, 0, sub[v] - 1);
array<long long, 2> cur = get(path[v]->mini);
u = par[v];
x = cur[0] - prv[0];
y = cur[1] - prv[1];
}
}
long long query() {
array<long long, 4> mini = path[1]->mini;
return *min_element(mini.begin(), mini.end());
}
void initialize(int n, vector<int> a, vector<int> b) {
for (int i = 0; i < n - 1; ++i) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
fill(type, type + n + 1, -1);
head[1] = 1;
dfs_sub(1);
dfs_hld(1);
dfs_build(1);
}
int cat(int u) {
update(u, 0, N);
type[u] = 0;
return query();
}
int dog(int u) {
update(u, N, 0);
type[u] = 1;
return query();
}
int neighbor(int u) {
if (type[u] == 0) {
update(u, 0, -N);
} else {
update(u, -N, 0);
}
type[u] = -1;
return query();
}
