#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const ll INF=1e12;
struct ki{
ll dp[2][2];
ki(int a=0,int b=0,int c=0,int d=0){
dp[0][0]=a;
dp[0][1]=b;
dp[1][0]=c;
dp[1][1]=d;
}
};
ki operator+(const ki& x,const ki& y){
ki res=ki(INF,INF,INF,INF);
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
for(int l=0;l<2;l++){
res.dp[i][l]=min(res.dp[i][l],x.dp[i][j]+(j^k)+y.dp[k][l]);
}
}
}
}
return res;
}
struct segtree{
vector<ki>t;
int n;
void build(int v,int tl,int tr){
if(tl==tr){
t[v]=ki(0,INF,INF,0);
return;
}
int mid=(tl+tr)>>1ll;
build(v*2,tl,mid);
build(v*2+1,mid+1,tr);
t[v]=t[v*2]+t[v*2+1];
}
void upd(int v,int tl,int tr,int l,int x0,int x1){
if(tl==tr){
t[v].dp[0][0]+=x0;
t[v].dp[1][1]+=x1;
return;
}
int mid=(tl+tr)>>1ll;
if(l<=mid){
upd(v*2,tl,mid,l,x0,x1);
}
else{
upd(v*2+1,mid+1,tr,l,x0,x1);
}
t[v]=t[v*2]+t[v*2+1];
}
void init(int sz){
n=sz;
t.resize(sz*4);
build(1,1,n);
}
pair<int,int> get(){
pair<int,int>res;
res.first=min(t[1].dp[0][0],t[1].dp[0][1]);
res.second=min(t[1].dp[1][0],t[1].dp[1][1]);
return {min(res.first,res.second+1),min(res.first+1,res.second)};
}
}seg[N];
int n;
vector<int> g[N];
int c[N];
int pr[N];
int sz[N];
void dfs1(int x, int p){
pr[x]=p;
sz[x]=1;
for(auto i:g[x]){
if(i!=p){
dfs1(i,x);
sz[x]+=sz[i];
}
}
for(auto &i:g[x]){
if(i==p){
swap(g[x][g[x].size()-1],i);
g[x].pop_back();
break;
}
}
sort(g[x].begin(),g[x].end(),[](int x,int y){
return sz[x]>sz[y];
});
}
int tin=0;
int head[N];
int pos[N];
void dfs2(int x,int p,int cur){
pr[x]=cur;
if(sz[cur]==0){
head[cur]=p;
}
pos[x]=++sz[cur];
for(auto i:g[x]){
if(g[x].front()==i){
dfs2(i,x,cur);
}
else{
dfs2(i,x,tin++);
}
}
}
void initialize(int _n, vector<int> a, vector<int> b){
n = _n;
for (int i = 0; i < n-1; i++){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
dfs1(1,0);
memset(pr,0,sizeof(pr));
memset(sz,0,sizeof(sz));
dfs2(1,0,tin++);
// for(int i=1;i<=n;i++){
// cout<<pos[i]<<' '<<pr[i]<<' '<<sz[pr[i]]<<' '<<i<<'\n';
// }
for(int i=0;i<tin;i++){
seg[i].init(sz[i]);
}
}
int upd(int x,int x0,int x1){
while(x!=0){
int cur=pr[x];
auto [a0,a1]=seg[cur].get();
seg[cur].upd(1,1,sz[cur],pos[x],x0,x1);
auto [b0,b1]=seg[cur].get();
x0=b0-a0;
x1=b1-a1;
x=head[cur];
}
auto [a,b]=seg[0].get();
return min(a,b);
}
int cat(int v){
c[v]=1;
int res=upd(v,N,0);
return res;
}
int dog(int v){
c[v]=2;
int res=upd(v,0,N);
return res;
}
int neighbor(int v){
int res=0;
if(c[v]==1){
res=upd(v,-N,0);
}
if(c[v]==2){
res=upd(v,0,-N);
}
c[v]=0;
return res;
}
