#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
const int64_t inf = 1e15;
struct Node {
int64_t dp[2][2];
};
struct SegT
{
vector<Node> seg;
int64_t n;
int64_t s;
SegT() {
}
SegT(int64_t _n) {
n=_n;
s=1;
while (s<n)s*=2;
seg.resize(2*s);
for (int64_t 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 (int64_t i = s-1; i; i--)
upd(i);
}
void upd(int64_t i) {
seg[i].dp[0][0]=seg[i].dp[1][1]=inf;
seg[i].dp[0][1]=seg[i].dp[1][0]=inf;
for (int64_t a = 0; a < 2; a++)
for (int64_t b = 0; b < 2; b++)
for (int64_t c = 0; c < 2; c++)
for (int64_t 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(int64_t& mc, int64_t& ps) {
int64_t a = min(seg[1].dp[0][0],seg[1].dp[0][1]);
int64_t b = min(seg[1].dp[1][0],seg[1].dp[1][1]);
ps=min(a, b+1);
mc=min(a+1, b);
}
void add(int64_t i, int64_t dc, int64_t dp) {
i+=s;
seg[i].dp[0][0]+=dp;
seg[i].dp[1][1]+=dc;
while (i)
{
upd(i);
i/=2;
}
}
};
vector<int64_t> graf[100005];
int64_t hut[100005];
int64_t par[100005];
int64_t heavy[100005];
int64_t gl[100005];
int64_t skp[100005];
int64_t skpar[100005];
int64_t hsz[100005];
int64_t pos[100005];
int64_t m;
SegT seg[100005];
int64_t dfs(int64_t u)
{
int64_t sz = 1, mx_sz = 0;
for (int64_t v:graf[u]) {
if (v == par[v]) continue;
par[v]=u;
gl[v]=gl[u]+1;
int64_t t_sz = dfs(v);
if (t_sz > mx_sz)
mx_sz=t_sz, heavy[u]=v;
sz+=t_sz;
}
return sz;
}
void hld(int64_t u, int64_t id)
{
skp[u]=id;
if (hsz[id]==0)
skpar[id]=par[u];
pos[u]=hsz[id]++;
if (heavy[u] != -1)
hld(heavy[u], id);
for (int64_t v:graf[u]) {
if (v==heavy[u] || v == par[u]) continue;
hld(v, m++);
}
}
int64_t upd(int64_t v, int64_t dp, int64_t dm) {
while (v!=-1)
{
int64_t t_sk = skp[v];
int64_t cm, cp;
seg[t_sk].get(cm, cp);
seg[t_sk].add(pos[v], dm, dp);
int64_t nm, np;
seg[t_sk].get(nm, np);
dm = nm-cm;
dp = np-cp;
v=skpar[v];
}
int64_t 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 (int64_t 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++);
skpar[0] = -1;
for (int64_t 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--;
int64_t 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;
}
