#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e5+5;
vector<int> adj[maxn];
int n;
int par[22][maxn];
int dep[maxn];
int cnt[maxn];
int pref[maxn];
int pos[maxn];
int head[maxn];
int tail[maxn];
ii per[maxn];
void dfs(int u = 1, int p = 0)
{
dep[u] = dep[p]+1;
par[0][u] = p;
cnt[u] = 1;
for(int i = 1; i<= 20; i++) par[i][u] = par[i-1][par[i-1][u]];
ii big = {0, -1};
for(int v : adj[u])
{
if(v == p) continue;
dfs(v, u);
cnt[u] += cnt[v];
big = max(big, {cnt[v], v});
}
pref[u] = big.Y;
}
void hld()
{
int tim = 1;
for(int i = 1; i<= n; i++)
{
if(pref[par[0][i]] == i) continue;
for(int j = i; j != -1; j = pref[j])
{
head[j] = i;
pos[j] = tim++;
tail[i] = j;
}
}
}
struct node
{
int val[4];
node()
{
memset(val, 0, sizeof val);
}
node operator + (node &other) const
{
node res;
for(int i = 0; i< 4; i++) res.val[i] = 1e9;
for(int i = 0; i< 4; i++)
{
int b1 = (i&2)> 0;
int b2 = (i&1)> 0;
for(int j = 0; j< 4; j++)
{
int b3 = (j&2)> 0;
int b4 = (j&1)> 0;
res.val[b1*2+b4] = min(res.val[b1*2+b4], val[i]+other.val[j]+(b2!= b3));
}
}
return res;
}
};
node st[4*maxn];
void build(int p = 1, int L = 1, int R = n)
{
if(L == R)
{
st[p] = node();
st[p].val[1] = st[p].val[2] = 1e9;
return;
}
int M = (L+R)>>1;
build(p<<1, L, M);
build(p<<1|1, M+1, R);
st[p] = st[p<<1]+st[p<<1|1];
}
void update(int x, ii v, int p = 1, int L = 1, int R = n)
{
if(L == R)
{
st[p].val[0] += v.X;
st[p].val[3] += v.Y;
return;
}
int M = (L+R)>>1;
if(x<= M) update(x, v, p<<1, L, M);
else update(x, v, p<<1|1, M+1, R);
st[p] = st[p<<1] + st[p<<1|1];
}
node ask(int i, int j, int p = 1, int L = 1, int R = n)
{
if(i> R || j< L)
{
node res;
res.val[1] = res.val[2] = 1e9;
return res;
}
if(i<= L && R<= j) return st[p];
int M = (L+R)>>1;
node x = ask(i, j, p<<1, L, M);
node y = ask(i, j, p<<1|1, M+1, R);
return x+y;
}
void change(int u, ii x)
{
// printf("change %d\n", u);
while(u)
{
// printf("go %d {%d, %d}\n", u, x.X, x.Y);
update(pos[u], x);
node tmp = ask(pos[head[u]], pos[tail[head[u]]]);
// for(int i = 0; i< 4; i++) printf("%d ", tmp.val[i]);
// printf("\n");
int v0 = min(tmp.val[0], tmp.val[1]);
int v1 = min(tmp.val[2], tmp.val[3]);
ii res = {min(v0, v1+1), min(v0+1, v1)};
x = ii(res.X-per[head[u]].X, res.Y-per[head[u]].Y);
per[head[u]] = res;
u = par[0][head[u]];
}
}
int gimme()
{
node res = ask(pos[1], pos[tail[1]]);
return *min_element(res.val, res.val+4);
}
void initialize(int N, vector<int> A, vector<int> B)
{
n = N;
for(int i = 0; i< n-1; i++)
{
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
dfs(); hld();
build();
}
int stat[maxn];
int cat(int u)
{
stat[u] = 1;
change(u, {0, 1e9});
return gimme();
}
int dog(int u)
{
stat[u] = 2;
change(u, {1e9, 0});
return gimme();
}
int neighbor(int u)
{
if(stat[u] == 1) change(u, {0, -1e9});
if(stat[u] == 2) change(u, {-1e9, 0});
stat[u] = 0;
return gimme();
}
