#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e5 + 7;
const int INF = (int) 1e8;
int n, sub[N], child[N], color[N], par[N], y, dp1[N], dp2[N], cost1[N], cost2[N], theindex[N], curind, node[N], l1[N], l2[N];
vector<int> members[N];
bool isTheChild[N];
vector<int> g[N];
struct D {
bool nmc;
int cost[2][2];
};
D operator + (D a, D b) {
if (a.nmc) {
return b;
}
if (b.nmc) {
return a;
}
D c;
c.nmc = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c.cost[i][j] = INF;
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
for (int l = 0; l < 2; l++) {
c.cost[i][l] = min(c.cost[i][l], a.cost[i][j] + b.cost[k][l] + (j != k));
}
}
}
}
return c;
}
D t[4 * N];
D wnmc;
void upd(int v, int tl, int tr, int i) {
if (tr < i || i < tl) {
return;
}
if (tl == tr) {
vector<int> K = {cost1[node[i]] + dp1[node[i]], cost2[node[i]] + dp2[node[i]]};
t[v].cost[0][1] = t[v].cost[1][0] = INF;
t[v].cost[0][0] = K[0];
t[v].cost[1][1] = K[1];
return;
}
int tm = (tl + tr) / 2;
upd(2 * v, tl, tm, i);
upd(2 * v + 1, tm + 1, tr, i);
t[v] = t[2 * v] + t[2 * v + 1];
}
D get(int v, int tl, int tr, int l, int r) {
if (tr < l || r < tl) {
return wnmc;
}
if (l <= tl && tr <= r) {
return t[v];
}
int tm = (tl + tr) / 2;
D x = get(2 * v, tl, tm, l, r);
D y = get(2 * v + 1, tm + 1, tr, l, r);
D z = x + y;
return x + y;
}
void buildtr(int v = 1, int tl = 0, int tr = n) {
if (tl == tr) {
t[v].cost[0][1] = t[v].cost[1][0] = INF;
t[v].cost[0][0] = t[v].cost[1][1] = 0;
} else {
int tm = (tl + tr) / 2;
buildtr(2 * v, tl, tm);
buildtr(2 * v + 1, tm + 1, tr);
t[v] = t[2 * v] + t[2 * v + 1];
}
}
void build(int a, int p = 0) {
vector<int> kids;
sub[a] = 1;
par[a] = p;
for (auto &b : g[a]) {
if (b != p) {
kids.push_back(b);
build(b, a);
sub[a] += sub[b];
if (sub[b] > sub[child[a]]) {
child[a] = b;
}
}
}
isTheChild[child[a]] = 1;
g[a] = kids;
}
void compute(int a) {
if (isTheChild[a]) {
color[a] = color[par[a]];
} else {
color[a] = ++y;
}
theindex[a] = ++curind;
node[theindex[a]] = a;
members[color[a]].push_back(a);
if (child[a]) {
compute(child[a]);
for (auto &b : g[a]) {
if (b != child[a]) {
compute(b);
}
}
}
}
void updVertex(int v) {
int p = par[members[color[v]][0]];
dp1[p] -= l1[color[v]];
dp2[p] -= l2[color[v]];
upd(1, 0, n, theindex[v]);
D sol = get(1, 0, n, theindex[members[color[v]][0]], theindex[members[color[v]].back()]);
l1[color[v]] = min(sol.cost[0][0], sol.cost[0][1]);
l2[color[v]] = min(sol.cost[1][0], sol.cost[1][1]);
l1[color[v]] = min(l1[color[v]], l2[color[v]] + 1);
l2[color[v]] = min(l2[color[v]], l1[color[v]] + 1);
dp1[p] += l1[color[v]];
dp2[p] += l2[color[v]];
}
void update(int node) {
while (node) {
updVertex(node);
node = par[members[color[node]][0]];
}
}
void initialize(int nn, std::vector<int> edgesA, std::vector<int> edgesB) {
wnmc.nmc = 1;
n = nn;
buildtr();
for (int i = 0; i < n - 1; i++) {
int a = edgesA[i];
int b = edgesB[i];
g[a].push_back(b);
g[b].push_back(a);
}
build(1);
compute(1);
}
void changeCost(int v, int c1, int c2) {
dp1[v] -= cost1[v];
dp2[v] -= cost2[v];
cost1[v] = c1;
cost2[v] = c2;
dp1[v] += cost1[v];
dp2[v] += cost2[v];
updVertex(v);
update(v);
}
int eval() {
return min(dp1[0], dp2[0]);
}
int cat(int v) {
changeCost(v, 0, INF);
return eval();
}
int dog(int v) {
changeCost(v, INF, 0);
return eval();
}
int neighbor(int v) {
changeCost(v, 0, 0);
return eval();
}
