#include "catdog.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#define N 111111
int col[N];
struct Mat{
int a[4];
friend Mat operator*(const Mat &a, const Mat &b) {
Mat c;
c.a[0] = std::min(a.a[0] + b.a[0], a.a[1] + b.a[2]);
c.a[1] = std::min(a.a[0] + b.a[1], a.a[1] + b.a[3]);
c.a[2] = std::min(a.a[2] + b.a[0], a.a[3] + b.a[2]);
c.a[3] = std::min(a.a[2] + b.a[1], a.a[3] + b.a[3]);
return c;
}
void pt() {
return ;
printf(" [ %d %d %d %d]\n",a[0],a[1],a[2],a[3]);
}
};
struct LCT {
struct{
int c[2],pa;
Mat val,prod;
} t[N];
int nrt(int v){return t[t[v].pa].c[0]==v||t[t[v].pa].c[1]==v;}
void pushup(int v){
if(!v)return;
if(t[v].c[0]&&t[v].c[1])t[v].prod=t[t[v].c[1]].prod*t[v].val*t[t[v].c[0]].prod;
else if(t[v].c[0])t[v].prod=t[v].val*t[t[v].c[0]].prod;
else if(t[v].c[1])t[v].prod=t[t[v].c[1]].prod*t[v].val;
else t[v].prod=t[v].val;
}
void rot(int v){
int p=t[v].pa,g=t[p].pa,d=t[p].c[1]==v;
if(t[v].c[!d])t[t[v].c[!d]].pa=p;
t[p].c[d]=t[v].c[!d];
t[v].c[!d]=p;
t[p].pa=v;t[v].pa=g;
pushup(p),pushup(v);
}
void splay(int v){
for(int p,g;nrt(v);rot(v)){
g=t[p=t[v].pa].pa;
if(nrt(p))rot((t[g].c[1]==p)==(t[p].c[1]==v)?p:v);
}
pushup(v);
}
void access(int v){
for(int w=0;v;v=t[w=v].pa){
splay(v);
t[v].val.a[0]+=std::min(t[t[v].c[1]].prod.a[0],t[t[v].c[1]].prod.a[3]+1);
t[v].val.a[2]+=std::min(t[t[v].c[1]].prod.a[0],t[t[v].c[1]].prod.a[3]+1)+1;
t[v].val.a[1]+=std::min(t[t[v].c[1]].prod.a[3],t[t[v].c[1]].prod.a[0]+1)+1;
t[v].val.a[3]+=std::min(t[t[v].c[1]].prod.a[3],t[t[v].c[1]].prod.a[0]+1);
t[v].val.a[0]-=std::min(t[w].prod.a[0],t[w].prod.a[3]+1);
t[v].val.a[2]-=std::min(t[w].prod.a[0],t[w].prod.a[3]+1)+1;
t[v].val.a[1]-=std::min(t[w].prod.a[3],t[w].prod.a[0]+1)+1;
t[v].val.a[3]-=std::min(t[w].prod.a[3],t[w].prod.a[0]+1);
t[v].c[1]=w;
pushup(v);
}
}
void link(int v,int w){
access(v);
splay(v);
t[v].pa=w;
}
}lc;
int n;
void initialize(int N_, std::vector<int> A, std::vector<int> B) {
static int qu[N+1],hd,tl,lv[N+1];
std::vector<std::vector<int>>g(N+1);
n=N_;
for(int i=0;i+1<n;++i){
g[A[i]+1].push_back(1+B[i]),g[1+B[i]].push_back(A[i]+1);
}
for(int i=1;i<=n;++i) lv[i]=0;
qu[tl=0]=hd=1;
while(hd-tl){
int u=qu[tl++];
lv[u]=1;
for(auto v:g[u])if(lv[v]==0)lv[v]=1,qu[hd++]=v,lc.link(v,u);
}
for(int i=1;i<=n;++i){
lc.access(i);
lc.splay(i);
lc.t[i].val.a[1]=lc.t[i].val.a[2]=1;
lc.pushup(i);
}
g.clear();
}
void ski(int v,int m){
lc.access(v);
lc.splay(v);
if(col[v]==1){
lc.t[v].val.a[1]+=m*1e8;
lc.t[v].val.a[3]+=m*1e8;
}else if(col[v]==2){
lc.t[v].val.a[0]+=m*1e8;
lc.t[v].val.a[2]+=m*1e8;
}else{
}
lc.pushup(v);
}
int getans(){
lc.access(1);
lc.splay(1);
lc.t[1].prod.pt();
return std::min(lc.t[1].prod.a[0],lc.t[1].prod.a[3]);
}
int cat(int v) {
++v;
ski(v,-1);
col[v]=1;
ski(v,1);
for (int i=1;i<=n;++i){
lc.access(i);
lc.splay(i);
lc.t[i].val.pt();
}
return getans();
}
int dog(int v) {
++v;
ski(v,-1);
col[v]=2;
ski(v,1);
for (int i=1;i<=n;++i){
lc.access(i);
lc.splay(i);
lc.t[i].val.pt();
}
return getans();
}
int neighbor(int v) {
++v;
ski(v,-1);
col[v]=0;
ski(v,1);
return getans();
}
