#include "catdog.h"
#include <bits/stdc++.h>
#define MN 100071
using namespace std;
int n, Sz[MN];
vector<int> L[MN];
const int kInf = numeric_limits<int>::max() / 4;
struct mat {
int v[2][2];
mat() {
v[0][0] = v[1][1] = 0;
v[0][1] = v[1][0] = kInf;
}
mat(int a, int b, int c, int d) {
v[0][0] = a, v[0][1] = b, v[1][0] = c, v[1][1] = d;
}
} I;
void afis(mat a);
namespace AINT {
mat uni(const mat &a, const mat &b) {
mat re(kInf, kInf, kInf, kInf);
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j)
for(int k = 0; k < 2; ++k)
for(int w = 0; w < 2; ++w)
re.v[i][w] = min(re.v[i][w], a.v[i][j] + b.v[k][w] + (j ^ k));
return re;
}
mat V[4 * MN];
int len;
void init() {
//for(int i = 0; i < 4 * MN; ++i) V[i] = r0;
}
void update(int p, mat v, int u = 1, int s = 1, int d = len) {
if(d < p || p < s) return;
if(s == d) {
V[u] = v;
//printf("Starea nodului %d(%d, %d) din AINT:\n", u, s, d);
afis(V[u]);
//printf("||||||||||||||\n");
return;
}
update(p, v, u << 1, s, (s + d) >> 1);
update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u] = uni(V[u << 1], V[u << 1 | 1]);
//printf("Starea nodului %d(%d, %d) din AINT:\n", u, s, d);
afis(V[u]);
//printf("||||||||||||||\n");
}
mat query(int l, int r, int u = 1, int s = 1, int d = len) {
if(r < s || d < l) return I;
if(l <= s && d <= r) {
return V[u];
}
int mij = (s + d) >> 1;
if(r <= mij) return query(l, r, u << 1, s, (s + d) >> 1);
if(mij < l) return query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
return uni(query(l, r, u << 1, s, (s + d) >> 1), query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d));
}
}
int Par[MN], In[MN], Out[MN], tmr, Nxt[MN];
int CFD[MN][2]; //cost fii secundari
int TipHut[MN];
void recalc_mat(int u) {
mat re;
if(TipHut[u] == 0) {
re.v[0][0] = 0;
re.v[1][1] = kInf;
}
if(TipHut[u] == 1) {
re.v[0][0] = kInf;
re.v[1][1] = 0;
}
if(TipHut[u] == 2) {
re.v[0][0] = 0;
re.v[1][1] = 0;
}
re.v[0][1] = kInf;
re.v[1][0] = kInf;
re.v[0][0] += CFD[u][0];
re.v[1][1] += CFD[u][1];
//printf(" !!! Pt nodul %d am recalc matricea:\n", u);
afis(re);
//printf("\n\n");
AINT::update(In[u], re);
}
void afis(mat a) {
//printf("%d %d\n%d %d\n", a.v[0][0], a.v[0][1], a.v[1][0], a.v[1][1]);
}
void propag(int u, int factor) {
while(u) {
int head = Nxt[u];
int tail = Out[head];
int par = Par[head];
mat rez = AINT::query(In[head], In[tail]);
//printf("u %d head %d tail %d par %d mat:\n", u, head, tail, par);
afis(rez);
//printf("---\n");
CFD[par][0] += factor * min(min(rez.v[0][0], rez.v[0][1]), 1 + min(rez.v[1][0], rez.v[1][1]));
CFD[par][1] += factor * min(1 + min(rez.v[0][0], rez.v[0][1]), min(rez.v[1][0], rez.v[1][1]));
if(factor == 1) recalc_mat(par);
u = par;
}
}
void update(int u) {
//printf("Update la %d cu tip %d\n", u, TipHut[u]);
propag(u, -1);
recalc_mat(u);
propag(u, 1);
}
void dfs_sz(int u, int p) {
Sz[u] = 1;
for(auto &it : L[u]) if(it != p) {
dfs_sz(it, u);
Sz[u] += Sz[it];
if(L[u][0] == p || Sz[it] > Sz[L[u][0]]) swap(it, L[u][0]);
}
}
void dfs_hld(int u, int p) {
Par[u] = p;
In[u] = ++tmr;
if(p) {
Nxt[u] = (u == L[p][0] ? Nxt[p] : u);
} else Nxt[u] = u;
Out[Nxt[u]] = u;
for(auto it : L[u])
if(it != p) dfs_hld(it, u);
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for(int i = 0; i <= n; ++i)
TipHut[i] = 2;
for(int i = 0; i < int(A.size()); ++i)
L[A[i]].push_back(B[i]), L[B[i]].push_back(A[i]);
dfs_sz(1, 0);
AINT::init();
dfs_hld(1, 0);
AINT::len = tmr;
//printf("Nod %d S %d N %d P %d I %d\n", i, Sz[i], Nxt[i], Par[i], In[i]);
}
int rez() {
return min(CFD[0][0], CFD[0][1]);
}
int cat(int v) {
TipHut[v] = 0;
update(v);
return rez();
}
int dog(int v) {
TipHut[v] = 1;
update(v);
return rez();
}
int neighbor(int v) {
TipHut[v] = 2;
update(v);
return rez();
}
