#include "catdog.h"
#include<vector>
#include<algorithm>
#define N_ 101000
#define pii pair<int,int>
using namespace std;
int w[N_], n, par[N_], C[N_], HL[N_][2], INF = 1e9;
vector<int>E[N_], Ch[N_];
struct Mat {
int A[2][2];
Mat() {
for (int i = 0; i < 2; i++)for (int j = 0; j < 2; j++)A[i][j] = 0;
}
};
Mat Merge(Mat a, Mat b) {
int i, k, j;
Mat T;
for (i = 0; i < 2; i++)for (j = 0; j < 2; j++)T.A[i][j] = INF;
for (i = 0; i < 2; i++) for (k = 0; k < 2; k++) for (j = 0; j < 2; j++) T.A[i][j] = min(T.A[i][j], a.A[i][k] + b.A[k][j]);
return T;
}
struct Tree {
vector<int>V;
vector<Mat>IT;
vector<pii>U;
int n, sz;
void UDT(int nd) {
IT[nd] = Merge(IT[nd * 2], IT[nd * 2 + 1]);
}
void init(int nd, int b, int e) {
if (b == e) {
IT[nd].A[0][0] = IT[nd].A[1][1] = 0;
IT[nd].A[0][1] = IT[nd].A[1][0] = 1;
return;
}
int m = (b + e) >> 1;
init(nd * 2, b, m);
init(nd * 2 + 1, m + 1, e);
UDT(nd);
}
void init() {
if (V.empty())return;
n = V.size();
U.resize(n);
sz = 1;
while (sz <= n)sz *= 2;
IT.resize(sz * 2);
init(1, 0, n - 1);
}
void Put(int nd, int b, int e, int x, int cur) {
if (b == e) {
IT[nd].A[0][0] = U[b].first;
IT[nd].A[1][1] = U[b].second;
IT[nd].A[0][1] = U[b].first + 1;
IT[nd].A[1][0] = U[b].second + 1;
if (cur == 1) IT[nd].A[1][0] = IT[nd].A[1][1] = INF;
if (cur == 2) IT[nd].A[0][0] = IT[nd].A[0][1] = INF;
return;
}
int m = (b + e) >> 1;
if (x <= m)Put(nd * 2, b, m, x, cur);
else Put(nd * 2 + 1, m + 1, e, x, cur);
UDT(nd);
}
pii Get() {
return { min(IT[1].A[0][0],IT[1].A[1][0]), min(IT[1].A[0][1], IT[1].A[1][1]) };
}
void Put(int x, int cur) {
Put(1, 0, n - 1, x, cur);
}
}T[N_];
void DFS(int a, int pp) {
par[a] = pp;
C[a] = 1;
for (auto &x : E[a]) {
if (x == pp)continue;
DFS(x, a);
Ch[a].push_back(x);
C[a] += C[x];
}
}
void HLD(int a, int ppp) {
T[ppp].V.push_back(a);
int pv = -1, Mx = -1;
for (auto &x : Ch[a]) {
if (Mx < C[x]) {
Mx = C[x];
pv = x;
}
}
if (pv == -1)return;
HLD(pv, ppp);
for (auto &x : Ch[a]) {
if(x!=pv)HLD(x, x);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
int i;
for (i = 0; i < n - 1; i++) {
E[A[i]].push_back(B[i]);
E[B[i]].push_back(A[i]);
}
DFS(1, 0);
HLD(1, 1);
for (i = 1; i <= n; i++) {
if (T[i].V.empty())continue;
reverse(T[i].V.begin(), T[i].V.end());
for (int j = 0; j < T[i].V.size(); j++) {
int a = T[i].V[j];
HL[a][0] = i, HL[a][1] = j;
}
T[i].init();
}
}
void Add(int v, pii bef, pii aft) {
int fi = aft.first - bef.first;
int se = aft.second - bef.second;
int a = HL[v][0], b = HL[v][1];
T[a].U[b].first += fi;
T[a].U[b].second += se;
}
int Go(int v, int ck) {
int a = HL[v][0], b = HL[v][1];
w[v] = ck;
while (1) {
pii bef = T[a].Get();
T[a].Put(b, ck);
pii aft = T[a].Get();
int pp = par[a];
if (!pp)break;
Add(pp, bef, aft);
a = HL[pp][0], b = HL[pp][1];
ck = w[pp];
}
pii z = T[1].Get();
return min(z.first, z.second);
}
int cat(int v) {
return Go(v, 1);
}
int dog(int v) {
return Go(v, 2);
}
int neighbor(int v) {
return Go(v, 0);
}
