#include<bits/stdc++.h>
#include "catdog.h"
using namespace std;
using pii = pair<int, int>;
#define Mp make_pair
#define X first
#define Y second
#define pb push_back
#define mins(a,b) (a = min(a,b))
#define lc id<<1
#define rc lc|1
#define mid ((l+r)/2)
const int MXN = 1e5+5;
const int INF = 1e9;
int n;
struct node {int dp[2][2];} seg[MXN<<2];
node merge(node x, node y) {
node res;
for(int i : {0,1})
for(int j : {0,1})
res.dp[i][j] = INF;
for(bool i : {0,1})
for(bool j : {0,1})
for(bool k : {0,1})
for(bool l : {0,1})
mins(res.dp[i][l], x.dp[i][j]+y.dp[k][l]+(j!=k));
return res;
}
namespace Seg {
void build(int l=0, int r=n, int id=1) {
if(r-l == 1) {
seg[id].dp[0][0] = seg[id].dp[1][1] = 0;
seg[id].dp[0][1] = seg[id].dp[1][0] = INF;
return;
}
build(l, mid, lc);
build(mid, r, rc);
seg[id] = merge(seg[lc], seg[rc]);
}
void upd(int p, pii x, int l=0, int r=n, int id=1) {
if(r-l==1) {
seg[id].dp[0][0] += x.X;
seg[id].dp[1][1] += x.Y;
return;
}
if(p<mid) upd(p, x, l, mid, lc);
else upd(p, x, mid, r, rc);
seg[id] = merge(seg[lc], seg[rc]);
}
node get(int s, int e, int l=0, int r=n, int id=1) {
if(s<=l && r<=e) return seg[id];
if(e<=mid) return get(s, e, l, mid, lc);
if(s>=mid) return get(s, e, mid, r, rc);
return merge(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}
}
int sz[MXN], par[MXN], stt[MXN], fnt[MXN], head[MXN], timer;
bool is_cat[MXN], is_dog[MXN];
vector<int> g[MXN];
void dfs1(int v) {
sz[v] = 1;
for(int u : g[v])
if(u^par[v]) {
par[u] = v;
dfs1(u);
sz[v] += sz[u];
}
}
void dfs2(int v) {
if(!head[v]) head[v] = v;
stt[v] = timer++;
fnt[v] = timer;
int big=-1;
for(int u : g[v])
if(u!=par[v] && (big==-1 || sz[big]<sz[u]))
big = u;
if(big != -1) {
head[big] = head[v];
dfs2(big);
fnt[v] = fnt[big];
}
for(int u : g[v])
if(u!=par[v] && u!=big)
dfs2(u);
}
void upd(int v, int z) {
v = head[v];
if(v==1) return;
node d = Seg::get(stt[v], fnt[v]);
int C = min(d.dp[0][0], d.dp[0][1]);
int D = min(d.dp[1][0], d.dp[1][1]);
Seg::upd(stt[par[v]], Mp(z*min(C,D+1), z*min(C+1,D)));
}
int ans() {
node d = Seg::get(stt[1], fnt[1]);
return min({d.dp[0][0], d.dp[0][1], d.dp[1][0], d.dp[1][1]});
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for(int i=0; i<n-1; i++) g[A[i]].pb(B[i]), g[B[i]].pb(A[i]);
dfs1(1);
dfs2(1);
Seg::build();
}
int cat(int v) {
is_cat[v] = 1;
vector<int> stk;
for(int u=v; head[u]!=1; u=par[head[u]])
stk.pb(head[u]);
while(!stk.empty()) {
upd(stk.back(), -1);
stk.pop_back();
}
Seg::upd(stt[v], Mp(0, INF));
for(int u=v; head[u]!=1; u=par[head[u]])
upd(head[u], 1);
return ans();
}
int dog(int v) {
is_dog[v] = 1;
vector<int> stk;
for(int u=v; head[u]!=1; u=par[head[u]])
stk.pb(head[u]);
while(!stk.empty()) {
upd(stk.back(), -1);
stk.pop_back();
}
Seg::upd(stt[v], Mp(INF, 0));
for(int u=v; head[u]!=1; u=par[head[u]])
upd(head[u], 1);
return ans();
}
int neighbor(int v) {
if(is_cat[v]) {
is_cat[v] = 0;
vector<int> stk;
for(int u=v; head[u]!=1; u=par[head[u]])
stk.pb(head[u]);
while(!stk.empty()) {
upd(stk.back(), -1);
stk.pop_back();
}
Seg::upd(stt[v], Mp(0, -INF));
for(int u=v; head[u]!=1; u=par[head[u]])
upd(head[u], 1);
}
if(is_dog[v]) {
is_dog[v] = 0;
vector<int> stk;
for(int u=v; head[u]!=1; u=par[head[u]])
stk.pb(head[u]);
while(!stk.empty()) {
upd(stk.back(), -1);
stk.pop_back();
}
Seg::upd(stt[v], Mp(-INF, 0));
for(int u=v; head[u]!=1; u=par[head[u]])
upd(head[u], 1);
}
return ans();
}
