#include "catdog.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
using namespace std;
#define maxn 200005
ll n;
vector<ll> g[maxn];
ll ls[maxn],rs[maxn],root[maxn];
ll tsz = 0;
ll lik[maxn];
ll up[maxn],sub[maxn],in[maxn],csz[maxn],dpt[maxn],parent[maxn];
ll timer = 0;
struct node{
ll a[2][2];
void init(){a[0][0] = a[1][1] = 0; a[0][1] = a[1][0] = llinf;}
node(){init();}
};
node t[4*maxn];
node mrg(node a,node b){
node c;
for(ll i = 0;i<=1;i++){
for(ll j = 0;j<=1;j++){
c.a[i][j] = llinf;
for(ll k = 0;k<=1;k++){
for(ll l = 0;l<=1;l++){
c.a[i][j] = min(c.a[i][j],a.a[i][k]+b.a[l][j] + (k^l));
}
}
}
}
return c;
}
void dfs_siz(ll u,ll par){
sub[u] = 1; dpt[u] = dpt[par] + 1; parent[u] = par;
for(ll s : g[u]) if(s!=par) dfs_siz(s,u),sub[u]+=sub[s];
}
void dfs(ll u,ll par){
if(!up[u]) up[u] = u;
ll smax = 0;
for(ll s : g[u]){
if(s==par) continue;
if(sub[smax]<sub[s]) smax = s;
}
if(smax==0) return;
up[smax] = up[u];
dfs(smax,u);
for(ll s : g[u]){
if(s==par||s==smax) continue;
dfs(s,u);
}
}
void upd(ll &v,ll tl,ll tr,ll i,ll a,ll b){
if(!v) v = ++tsz;
if(tl==tr){t[v].a[0][0]+=a;t[v].a[1][1]+=b;return;}
ll mid = (tl+tr)/2;
if(i<=mid) upd(ls[v],tl,mid,i,a,b);
else upd(rs[v],mid+1,tr,i,a,b);
t[v] = mrg(t[ls[v]],t[rs[v]]);
}
pll val(ll v){
ll a = min(t[v].a[0][0],t[v].a[0][1]);
ll b = min(t[v].a[1][0],t[v].a[1][1]);
a = min(a,b+1);
b = min(b,a+1);
return {a,b};
}
void upd(ll u,ll a,ll b){
ll lb,la,nb,na;
while(u){
pll p = val(root[up[u]]);
la = p.fi; lb = p.sc;
upd(root[up[u]],1,csz[up[u]],dpt[u]-dpt[up[u]]+1,a,b);
p = val(root[up[u]]);
na = p.fi; nb = p.sc;
u = parent[up[u]];
a = na - la; b = nb - lb;
}
}
ll rez(){pll p = val(root[1]); return min(p.fi,p.sc);}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for(ll i = 0;i<n-1;i++){
ll x = A[i],y = B[i];
g[x].pb(y);
g[y].pb(x);
}
dfs_siz(1,0); dfs(1,0);
for(ll i = 1;i<=n;i++) csz[up[i]]++;
}
int cat(int v) {
upd(v,n,0);
lik[v] = 1;
return rez();
}
int dog(int v) {
upd(v,0,n);
lik[v] = 2;
return rez();
}
int neighbor(int v) {
if(lik[v]==1) upd(v,-n,0);
else upd(v,0,-n);
lik[v] = 0;
return rez();
}
/*
5
1 2
2 3
2 4
4 5
5
2 3
1 5
2 2
1 1
3 2
out:
0
1
0
2
1
*/
