#include "catdog.h"
#define M 100100
#include<bits/stdc++.h>
using namespace std;
int type[M],sz[M],id[M],top[M],out[M],hev[M],CC,par[M],osc[M],BG=1e9;
struct dpstruct{
int cc,cd,dc,dd;
dpstruct(){cc=dd=0,cd=dc=1;}
dpstruct(int x){cc=dd=0,cd=dc=BG;}
inline friend dpstruct operator +(dpstruct a,dpstruct b){
dpstruct c;
swap(a,b);
c.cc=min({a.cc+b.cc,a.cd+b.dc,BG});
c.cd=min({a.cc+b.cd,a.cd+b.dd,BG});
c.dc=min({a.dd+b.dc,a.dc+b.cc,BG});
c.dd=min({a.dd+b.dd,a.dc+b.cd,BG});
return c;
}
inline void sub(dpstruct x){
int dog=min(x.cd,x.dd);
int cat=min(x.cc,x.dc);
dog=min(dog,cat+1);
cat=min(cat,dog+1);
cc-=cat;
cd-=dog;
dc-=cat;
dd-=dog;
}
inline void add(dpstruct x){
int dog=min(x.cd,x.dd);
int cat=min(x.cc,x.dc);
dog=min(dog,cat+1);
cat=min(cat,dog+1);
cc+=cat;
cd+=dog;
dc+=cat;
dd+=dog;
}
inline int an(){return min({cc,cd,dc,dd});}
} T[1<<18],fl[M];
vector<int>adj[M];
dpstruct query(int i,int l,int r,int ll,int rr){
if(ll>r|l>rr)return dpstruct(0);
if(ll<=l&&r<=rr)return T[i];
return query(i*2,l,l+r>>1,ll,rr)+
query(i*2+1,l+r+2>>1,r,ll,rr);
}
void upd(int i,int l,int r,int p,dpstruct x){
if(l==r)return void(T[i]=x);
if(p<=l+r>>1)upd(i*2,l,l+r>>1,p,x);
else upd(i*2+1,l+r+2>>1,r,p,x);
T[i]=T[i*2]+T[i*2+1];
}
void dfs1(int n){
sz[n]=1;
for(auto i:adj[n]) if(i-par[n])
par[i]=n,dfs1(i),sz[n]+=sz[i],
hev[n]=(sz[hev[n]]<sz[i]?i:hev[n]);
}
void dfs2(int n){
osc[id[n]=++CC]=n;
top[n]=(n-hev[par[n]]?n:top[par[n]]);
out[top[n]]=CC;
if(hev[n])dfs2(hev[n]);
for(auto i:adj[n])
if(i-par[n]&&i-hev[n])
dfs2(i);
}
void initialize(int N, std::vector<int> A, std::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]);
dfs1(1);
dfs2(1);
}
dpstruct gedan(int chain){
return query(1,1,CC,id[top[chain]],out[top[chain]]);
}
dpstruct idk(int t,dpstruct x){
if(t>1)x.cc=x.dc=BG;
else if(t)x.cd=x.dd=BG;
return x;
}
void redo(int n){
if(!n)return;
fl[par[top[n]]].sub(gedan(n));
upd(1,1,CC,id[n],idk(type[n],fl[n]));
fl[par[top[n]]].add(gedan(n));
return redo(par[top[n]]);
}
int cat(int v) {
type[v]=1;
redo(v);
return gedan(1).an();
}
int dog(int v) {
type[v]=2;
redo(v);
return gedan(1).an();
}
int neighbor(int v) {
type[v]=0;
redo(v);
return gedan(1).an();
}
