#include "catdog.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
struct dak
{
int dp[2][2];
dak()
{
memset(dp, 0, sizeof(dp));
}
} nod[nx<<2];
dak operator +(dak a, dak b)
{
dak c;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
c.dp[i][j]=inf;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
for(int l = 0; l < 2; l++)
for(int r = 0; r < 2; r++)
c.dp[i][r]=min(c.dp[i][r], a.dp[i][j]+b.dp[l][r]+(j!=l));
return c;
}
vector<int> adj[nx];
int n;
int par[nx], sz[nx], ani[nx], leaf[nx], last[nx];
int top[nx], chain=1, id[nx], pos[nx], tim=0;
void dfs(int u)
{
sz[u]=1;
for(int v:adj[u])
{
if(v==par[u]) continue;
par[v]=u;
dfs(v);
sz[u]+=sz[v];
}
}
void hld(int u)
{
if(!top[chain]) top[chain]=u;
last[chain]=u;
id[u]=chain;
pos[u]=++tim;
int sp=-1;
for(int v:adj[u])
if(v!=par[u])
if(sp==-1 || sz[sp]<sz[v])
sp=v;
hld(sp);
for(int v:adj[u])
if(v!=par[u] && v!=sp)
chain++, hld(v);
}
void build(int id, int l, int r)
{
if(l==r) return void(leaf[l]=id);
int mid=(l+r)>>1;
build(id<<1, l, mid);
build(id<<1|1, mid+1, r);
}
void update(int p, int cat, int dog)
{
int id=leaf[p];
nod[id].dp[0][0]+=cat;
nod[id].dp[1][1]+=dog;
while(id>1)
{
id>>=1;
nod[id]=nod[id<<1]+nod[id<<1|1];
}
}
dak get(int id, int l, int r, int u, int v)
{
if(l>=u && r<=v) return nod[id];
int mid=(l+r)>>1;
if(v<=mid) return get(id<<1, l, mid, u, v);
if(u>mid) return get(id<<1|1, mid+1, r, u, v);
return get(id<<1, l, mid, u, v)+get(id<<1|1, mid+1, r, u, v);
}
void initialize(int N, vector<int> a, vector<int> b)
{
n=N;
for(int i = 0; i < n-1; i++)
{
adj[a[i]].emplace_back(b[i]);
adj[b[i]].emplace_back(a[i]);
}
for(int i = 1; i <= n; i++)
ani[i]=0;
dfs(1);
hld(1);
}
dak sus(dak a)
{
dak b;
b.dp[0][0]=min({a.dp[0][0], a.dp[0][1], a.dp[1][0]+1, a.dp[1][1]+1});
b.dp[1][1]=min({a.dp[1][1], a.dp[1][0], a.dp[0][1]+1, a.dp[0][0]+1});
return b;
}
dak answer(int u)
{
int t=top[id[u]];
return get(1, 1, n, pos[t], pos[last[id[u]]]);
}
void solve(int u, int cat, int dog)
{
while(u>0)
{
dak cur=sus(answer(u));
update(pos[u], cat, dog);
dak nw=sus(answer(u));
cat=nw.dp[0][0]-cur.dp[0][0];
dog=nw.dp[1][1]-cur.dp[1][1];
u=par[top[id[u]]];
}
}
int ha(dak a)
{
return min({a.dp[0][0], a.dp[0][1], a.dp[1][0], a.dp[1][1]});
}
int cat(int u)
{
ani[u]=1;
solve(u, 0, inf);
return ha(answer(1));
}
int dog(int u)
{
ani[u]=2;
solve(u, inf, 0);
return ha(answer(1));
}
int neighbor(int u)
{
if(ani[u]==1) solve(u, 0, -inf);
else solve(u, -inf, 0);
ani[u]=0;
return ha(answer(1));
}
// int main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// }
