#include "bits/stdc++.h"
#include "catdog.h"
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int inf = int(1E8);
struct M {
int a, b, c, d;
};
M operator+ (const M& lhs, const M& rhs) {
if (lhs.a == -1) {
return rhs;
}
if (rhs.a == -1) {
return lhs;
}
M res;
res.a = std::min({lhs.a + rhs.a,
lhs.a + rhs.c + 1,
lhs.b + rhs.a + 1,
lhs.b + rhs.c});
res.b = std::min({lhs.a + rhs.b,
lhs.a + rhs.d + 1,
lhs.b + rhs.b + 1,
lhs.b + rhs.d});
res.c = std::min({lhs.c + rhs.a,
lhs.c + rhs.c + 1,
lhs.d + rhs.a + 1,
lhs.d + rhs.c});
res.d = std::min({lhs.c + rhs.b,
lhs.c + rhs.d + 1,
lhs.d + rhs.b + 1,
lhs.d + rhs.d});
return res;
}
constexpr int max_N = int(1E5) + 5;
#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l) << 1)
struct segtree {
M tree[max_N << 1] {};
void build(int v, int l, int r) {
for (int i = (r - l); i < 2 * (r - l); ++i) {
tree[v + i] = {0, inf, inf, 0};
}
for (int i = (r - l) - 1; i >= 1; --i) {
tree[v + i] = tree[v + (i << 1)] + tree[v + (i << 1 | 1)];
}
}
void add(int v, int l, int r, int p, int x, int y) {
p += r - (l << 1);
tree[v + p].a += x;
tree[v + p].d += y;
while (p >>= 1) {
tree[v + p] = tree[v + (p << 1)] + tree[v + (p << 1 | 1)];
}
}
M get(int v, int l, int r, int ql, int qr) {
ql += r - (l << 1);
qr += r - (l << 1);
M resl = {-1, 0, 0, 0};
M resr = {-1, 0, 0, 0};
while (ql < qr) {
if (ql & 1) {
resl = resl + tree[v + ql];
ql++;
}
if (qr & 1) {
--qr;
resr = tree[v + qr] + resr;
}
ql >>= 1;
qr >>= 1;
}
M res = resl + resr;
return res;
}
int v_cnt = 0;
int s_cnt = 0;
void add_size(int x) {
build(v_cnt, s_cnt, s_cnt + x);
v_cnt += (x << 1);
s_cnt += x;
}
} seg;
int N;
std::vector<int> adj[max_N];
int tim = 0;
int siz[max_N];
int par[max_N];
int top[max_N];
int tin[max_N];
int tout[max_N];
int len[max_N];
int typ[max_N];
int roots[max_N];
int ubl[max_N];
int ubr[max_N];
void dfs1(int v) {
siz[v] = 1;
for (auto& u : adj[v]) {
adj[u].erase(std::find(adj[u].begin(), adj[u].end(), v));
par[u] = v;
dfs1(u);
siz[v] += siz[u];
if (siz[u] > siz[adj[v][0]]) {
std::swap(u, adj[v][0]);
}
}
}
void dfs2(int v) {
tin[v] = tim++;
for (auto u : adj[v]) {
if (u == adj[v][0]) {
top[u] = top[v];
len[top[v]] += 1;
} else {
top[u] = u;
len[u] = 1;
}
dfs2(u);
}
tout[v] = tim;
if (v == top[v]) {
roots[v] = seg.v_cnt;
ubl[v] = seg.s_cnt;
ubr[v] = ubl[v] + len[v];
seg.add_size(len[v]);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
::N = N;
for (int i = 0; i < N - 1; ++i) {
--A[i], --B[i];
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
par[0] = -1;
dfs1(0);
len[0] = 1;
dfs2(0);
// debug_tree();
debug();
}
void modify(int v, int x, int y) {
while (v != -1) {
debug(v, roots[top[v]], top[v], ubl[top[v]], ubr[top[v]], ubl[top[v]] + tin[v] - tin[top[v]], x, y);
M get_bef = seg.get(roots[top[v]], ubl[top[v]], ubr[top[v]], ubl[top[v]], ubr[top[v]]);
seg.add(roots[top[v]], ubl[top[v]], ubr[top[v]], ubl[top[v]] + tin[v] - tin[top[v]], x, y);
M get_nex = seg.get(roots[top[v]], ubl[top[v]], ubr[top[v]], ubl[top[v]], ubr[top[v]]);
v = par[top[v]];
x = std::min({get_nex.a, get_nex.b, get_nex.c + 1, get_nex.d + 1}) - std::min({get_bef.a, get_bef.b, get_bef.c + 1, get_bef.d + 1});
y = std::min({get_nex.a + 1, get_nex.b + 1, get_nex.c, get_nex.d}) - std::min({get_bef.a + 1, get_bef.b + 1, get_bef.c, get_bef.d});
}
}
int answer() {
debug(roots[0], ubl[0], ubr[0], ubl[0]);
M x = seg.get(roots[0], ubl[0], ubr[0], ubl[0], ubr[0]);
int res = std::min({x.a, x.b, x.c, x.d});
return res;
}
int cat(int v) {
--v;
modify(v, 0, inf);
typ[v] = 1;
return answer();
}
int dog(int v) {
--v;
modify(v, inf, 0);
typ[v] = 2;
return answer();
}
int neighbor(int v) {
--v;
if (typ[v] == 1) {
modify(v, 0, -inf);
} else {
modify(v, -inf, 0);
}
typ[v] = 0;
return answer();
}
