#include <bits/stdc++.h>
// #include "catdog.h"
using namespace std;
const int64_t inf = 1e5+5;
struct Node {
int64_t dp[2][2];
};
struct SegT
{
vector<Node> seg;
int n;
int s;
SegT() {
}
SegT(int _n) {
n=_n;
s=1;
while (s<n)s*=2;
seg.resize(2*s);
for (int i=s; i<2*s; i++) {
seg[i].dp[0][0]=seg[i].dp[1][1]=0;
seg[i].dp[0][1]=seg[i].dp[1][0]=inf;
}
for (int i = s-1; i; i--)
upd(i);
}
void upd(int i) {
seg[i].dp[0][0]=seg[i].dp[1][1]=inf;
seg[i].dp[0][1]=seg[i].dp[1][0]=inf;
for (int a = 0; a < 2; a++)
for (int b = 0; b < 2; b++)
for (int c = 0; c < 2; c++)
for (int d = 0; d < 2; d++)
seg[i].dp[a][d] = min(seg[i].dp[a][d], seg[i*2].dp[a][b]+
seg[i*2+1].dp[c][d]+(b!=c));
}
void get(int& mc, int& ps) {
int a = min(seg[1].dp[0][0],seg[1].dp[0][1]);
int b = min(seg[1].dp[1][0],seg[1].dp[1][1]);
ps=min(a, b+1);
mc=min(a+1, b);
}
void add(int i, int dc, int dp) {
i+=s;
seg[i].dp[0][0]+=dp;
seg[i].dp[1][1]+=dc;
while (i)
{
upd(i);
i/=2;
}
}
};
vector<int> graf[100005];
int hut[100005];
int par[100005];
int heavy[100005];
int gl[100005];
int skp[100005];
int hsz[100005];
int pos[100005];
int m;
SegT seg[100005];
int dfs(int u)
{
int sz = 1, mx_sz = 0;
for (int v:graf[u]) {
if (v == par[v]) continue;
par[v]=u;
gl[v]=gl[u]+1;
int t_sz = dfs(v);
if (t_sz > mx_sz)
mx_sz=t_sz, heavy[u]=v;
sz+=t_sz;
}
return sz;
}
void hld(int u, int id)
{
skp[u]=id;
pos[u]=hsz[id]++;
if (heavy[u] != -1)
hld(heavy[u], id);
for (int v:graf[u]) {
if (v==heavy[u] || v == par[u]) continue;
hld(v, m++);
}
}
int upd(int v, int dm, int dp) {
while (1)
{
int t_sk = skp[v];
int cm, cp;
seg[t_sk].get(cm, cp);
seg[t_sk].add(pos[v], dm, dp);
int nm, np;
seg[t_sk].get(nm, np);
dm = nm-cm;
dp = np-cp;
if (v==0)
break;
}
int mc, p;
seg[0].get(mc, p);
return min(mc, p);
}
void initialize(int n, vector<int> a, vector<int> b)
{
memset(heavy, -1, sizeof(heavy));
for (int i = 0; i < n-1; i++)
{
graf[a[i]-1].push_back(b[i]-1);
graf[b[i]-1].push_back(a[i]-1);
}
dfs(0);
hld(0, m++);
for (int i = 0; i < m; i++)
seg[i] = SegT(hsz[i]);
}
int cat(int v)
{
v--;
hut[v] = 1;
return upd(v, 0, inf);
}
int dog(int v)
{
v--;
hut[v] = 2;
return upd(v, inf, 0);
}
int neighbor(int v)
{
v--;
int r = 0;
if (hut[v] == 1)
r = upd(v, 0, -inf);
else if (hut[v] == 2)
r = upd(v, -inf, 0);
hut[v] = 0;
return r;
}
// int main() {
// return 0;
// }
