#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
template<class T1, class T2>
bool maximize(T1 &a, T2 b){ if (a < b){ a = b; return true; } return false; }
template<class T1, class T2>
bool minimize(T1 &a, T2 b){ if (a > b){ a = b; return true; } return false; }
const ll INF = 1e18;
int n;
vector<int> adj[1000005];
int child[1000005], big[1000005];
int par[1000005], head[1000005], rev[1000005], pos[1000005], curPos, sz[1000005];
int cur[1000005];
void dfs(int u, int p){
child[u] = 1;
big[u] = -1;
for (auto v : adj[u]){
if (v == p) continue;
dfs(v, u);
child[u] += child[v];
if (big[u] == -1 || child[big[u]] < child[v]) big[u] = v;
}
}
void decompose(int u, int h, int p){
pos[u] = ++curPos;
par[u] = p;
rev[curPos] = u;
head[u] = h;
sz[h]++;
if (big[u] != -1) decompose(big[u], h, u);
for (auto v : adj[u]){
if (v == p || v == big[u]) continue;
decompose(v, v, u);
}
}
struct Node{
ll x[2][2];
};
Node combine(Node a, Node b){
Node res;
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
res.x[i][j] = 1e9;
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
for (int k = 0; k <= 1; k++)
for (int l = 0; l <= 1; l++)
res.x[i][j] = min(res.x[i][j], a.x[i][k] + b.x[l][j] + (k ^ l));
return res;
}
struct SegTree{
vector<Node> st;
int n;
void init(int _n){ n = _n; st.assign(4*n+5, {}); }
void build(int id, int l, int r){
if (l == r){
st[id].x[0][0] = st[id].x[1][1] = 0;
st[id].x[0][1] = st[id].x[1][0] = 1e9;
return;
}
int mid = (l + r) >> 1;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = combine(st[id*2], st[id*2+1]);
}
void update(int id, int l, int r, int p, int va, int vb){
if (l == r){
st[id].x[0][0] += va;
st[id].x[1][1] += vb;
return;
}
int mid = (l + r) >> 1;
if (p <= mid) update(id*2, l, mid, p, va, vb);
else update(id*2+1, mid+1, r, p, va, vb);
st[id] = combine(st[id*2], st[id*2+1]);
}
pair<int,int> get(){
int c = min(st[1].x[0][0], st[1].x[0][1]);
int d = min(st[1].x[1][1], st[1].x[1][0]);
return {min(c, d+1), min(c+1, d)};
}
};
SegTree seg[1000005];
void updatePath(int u, int va, int vb){
while (u){
int h = head[u];
auto [c, d] = seg[h].get();
seg[h].update(1, 1, sz[h], pos[u]-pos[h]+1, va, vb);
auto [c1, d1] = seg[h].get();
va = c1 - c;
vb = d1 - d;
u = par[h];
}
}
int cat(int x){
cur[x] = 1;
updatePath(x, 0, 1e9);
auto [c, d] = seg[1].get();
return min(c, d);
}
int dog(int x){
cur[x] = 2;
updatePath(x, 1e9, 0);
auto [c, d] = seg[1].get();
return min(c, d);
}
int neighbor(int x){
updatePath(x, -1e9*(cur[x] != 1), -1e9*(cur[x] != 2));
cur[x] = 0;
auto [c, d] = seg[1].get();
return min(c, d);
}
void initialize(int N, vector<int> A, vector<int> B){
n = N;
for (int i = 0; i < n-1; i++){
int u = A[i], v = B[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0);
decompose(1, 1, 0);
for (int i = 1; i <= n; i++){
if (head[i] == i){
seg[i].init(sz[i]);
seg[i].build(1, 1, sz[i]);
}
}
}
