#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=INT_MAX/3;
ll mmax=101010;
ll N,Q;
ll catdog[101010];
vector <ll> graph[101010];
priority_queue <pair<ll,ll> > pq[101010];
ll num[101010];
ll group[101010];
ll go[101010];
ll cnt,gnn,gtt;
struct node{
ll val[2][2];
void init(){
val[0][0]=val[1][1]=0;
val[0][1]=val[1][0]=INF;
}
void update(node a,node b){
for(ll i=0;i<2;i++)fill(val[i],val[i]+2,INF);
//puts("filled");
for(ll i=0;i<2;i++)for(ll j=0;j<2;j++)
for(ll x=0;x<2;x++)for(ll y=0;y<2;y++)//fuuuujkkkkk;
val[i][y]=min(val[i][y],a.val[i][j]+b.val[x][y]+(j^x));
//puts("hmmteresting");
//puts("fucking bald arn...");
}
};
struct SEG{
vector <node> tree;
ll sz;
void trit(ll l,ll r,ll m){
//printf("%lld %lld %lld\n",l,r,m);
if(l==r){
tree[m].init();
return;
}
ll mid=(l+r)/2;
trit(l,mid,m*2);
trit(mid+1,r,m*2+1);
tree[m].update(tree[m*2],tree[m*2+1]);
//printf("updated\n");
}
void init(ll n){
sz=n;
tree.resize(n*4);
if(sz)trit(1,sz,1);
}
void update(ll x,ll l,ll r,ll m,ll a,ll b){
if(x<l||x>r)return;
if(l==r){
tree[m].val[0][0]+=a;
tree[m].val[1][1]+=b;
return;
}
ll mid=(l+r)/2;
update(x,l,mid,m*2,a,b);
update(x,mid+1,r,m*2+1,a,b);
tree[m].update(tree[m*2],tree[m*2+1]);
}
pair<ll,ll> getf(){
ll a=min(tree[1].val[0][0],tree[1].val[0][1]);
ll b=min(tree[1].val[1][0],tree[1].val[1][1]);
return {min(a,b+1),min(a+1,b)};
}
};
SEG HLD[101010];
ll dfs1(ll now,ll par){
//printf("%lld\n",now);
for(auto i:graph[now])if(i!=par){
num[now]+=dfs1(i,now);
pq[now].push({num[i],i});
}
return ++num[now];
}
void dfs2(ll now,ll par){
if(!gnn){
gnn=++gtt;
go[gnn]=par;
}
group[now]=gnn;
num[now]=++cnt;
while(!pq[now].empty()){
dfs2(pq[now].top().second,now);
pq[now].top();
pq[now].pop();
}
HLD[gnn].init(cnt);
gnn=0;cnt=0;
//printf("%lld\n",now);
}
void initialize(int n,vector<int> A,vector<int> B) {
N=n;
for(int i=0;i<A.size();i++)graph[A[i]].push_back(B[i]);
for(int i=0;i<A.size();i++)graph[B[i]].push_back(A[i]);
dfs1(1,0);
dfs2(1,0);
}
void hldupdate(ll now,ll a,ll b){
while(now){
//printf("%lld\n",now);
pair<ll,ll> p=HLD[group[now]].getf();
HLD[group[now]].update(num[now],1,HLD[group[now]].sz,1,a,b);
pair<ll,ll> q=HLD[group[now]].getf();
a=q.first-p.first;
b=q.second-p.second;
now=go[group[now]];
}
}
int cat(int v){
hldupdate(v,mmax,0);
catdog[v]=1;
return min(HLD[1].getf().first,HLD[1].getf().second);
}
int dog(int v){
hldupdate(v,0,mmax);
catdog[v]=2;
return min(HLD[1].getf().first,HLD[1].getf().second);
}
int neighbor(int v){
if(catdog[v]==1)hldupdate(v,-mmax,0);
else hldupdate(v,0,-mmax);
catdog[v]=0;
return min(HLD[1].getf().first,HLD[1].getf().second);
}
