#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
struct node{
int s, e, m, val[2][2];
node *l, *r;
node(int S, int E){
s=S, e=E, m=(s+e)/2;
val[0][0]=val[1][1]=0;
val[0][1]=val[1][0]=INT_MAX/2;
if (s!=e){
val[0][1]=val[1][0]=1;
l = new node(s, m);
r = new node(m+1, e);
}
}
void up(int i, int a, int b){
if (s==e){
val[0][0]+=a;
val[1][1]+=b;
return;
}
if (i<=m)l->up(i, a, b);
else r->up(i, a, b);
val[0][0]=val[0][1]=val[1][0]=val[1][1]=INT_MAX/2;
for (int i=0; i<2; ++i)for (int j=0; j<2; ++j)for (int k=0; k<2; ++k)for (int p=0; p<2; ++p)val[i][j]=min(val[i][j], l->val[i][k]+r->val[p][j]+(p^k));
}
pii query(){
return mp(min(min(val[0][0], val[0][1]), min(val[1][1], val[1][0])+1), min(min(val[0][0], val[0][1])+1, min(val[1][1], val[1][0])));
}
}*st[100005];
int n, ccounter=0;
vector<int> par, heavy, head, chain, id, counter, vect;
vector<vector<int> > graph;
int dfs(int node, int p){
par[node]=p;
int sz=1, mx=0;
for (auto num:graph[node])if (num!=p){
int temp=dfs(num, node);
sz+=temp;
if (temp>mx)mx=temp, heavy[node]=num;
}
return sz;
}
void dfs2(int node, int h){
head[node]=h;
chain[node]=chain[h];
id[node]=counter[chain[node]]++;
if (heavy[node])dfs2(heavy[node], h);
for (auto num:graph[node])if (num!=par[node]&&num!=heavy[node])chain[num]=++ccounter, dfs2(num, num);
}
int update(int node, int a, int b){
pii res, temp;
for (;node!=-1;node=par[head[node]]){
temp=st[chain[node]]->query();
st[chain[node]]->up(id[node], a, b);
res=st[chain[node]]->query();
a=res.fi-temp.fi;
b=res.se-temp.se;
}
return min(res.fi, res.se);
}
void initialize(int N, vector<int> a, vector<int> b){
n=N;
vect.resize(n+1, 0);
id.resize(n+1);
counter.resize(n+1, 1);
head.resize(n+1, 1);
chain.resize(n+1, 0);
par.resize(n+1);
heavy.resize(n+1, 0);
graph.resize(n+1);
for (int i=0; i<n-1; ++i){
graph[a[i]].pb(b[i]);
graph[b[i]].pb(a[i]);
}
dfs(1, -1);
dfs2(1, 1);
for (int i=0; i<=ccounter; ++i)st[i] = new node(1, counter[i]-1);
}
int cat(int a){
vect[a]=1;
return update(a, 0, n);
}
int dog(int a){
vect[a]=2;
return update(a, n, 0);
}
int neighbor(int a){
if (vect[a]==1){
vect[a]=0;
return update(a, 0, -n);
}
vect[a]=0;
return update(a, -n, 0);
}
