#include<bits/stdc++.h>
#include "catdog.h"
using namespace std;
#define int long long
const int maxn = 1e5 + 5;
const int inf = 1e9;
struct Node {
int dp[2][2];
Node (int cat = 0, int dog = 0){
dp[0][0] = cat;
dp[1][1] = dog;
dp[0][1] = dp[1][0] = inf;
}
friend Node operator + (Node left, Node right){
Node ans = Node(inf, inf);
for (int l = 0; l < 2; l++){
for (int r = 0; r < 2; r++){
for (int a = 0; a < 2; a++){
for (int b = 0; b < 2; b++){
ans.dp[l][r] = min(ans.dp[l][r], left.dp[l][a] + right.dp[b][r] + (a ^ b));
}
}
}
}
return ans;
}
};
struct Segtree {
int n;
vector<Node> t;
Segtree(){}
Segtree(int _n){
n = _n;
t.resize((n << 2) + 1);
}
void update(int id, int l, int r, int pos, int cat, int dog){
if (l == r){
t[id].dp[0][0] += cat;
t[id].dp[1][1] += dog;
return;
}
else{
int m = (l + r) >> 1;
if (pos <= m) update(id << 1, l, m, pos, cat, dog);
else update(id << 1 | 1, m + 1, r, pos, cat, dog);
t[id] = t[id << 1] + t[id << 1 | 1];
}
}
void upd(int pos, int cat, int dog){
update(1, 1, n, pos, cat, dog);
}
int cat(){
return min(t[1].dp[0][1], t[1].dp[0][0]);
}
int dog(){
return min(t[1].dp[1][0], t[1].dp[1][1]);
}
};
int sz[maxn], head[maxn], inChain[maxn], par[maxn], id[maxn], type[maxn], cursz[maxn], tin[maxn], pre[2][maxn], timeDfs, Chain, n;
vector<int> ad[maxn];
Segtree st[maxn];
void dfs(int u, int p){
sz[u] = 1;
par[u] = p;
for (auto v : ad[u]){
if (v == p) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
void hld (int u, int p){
id[u] = Chain;
tin[u] = ++timeDfs;
if (!head[Chain]) head[Chain] = u;
if (cursz[Chain] = 0) cursz[Chain] = 1;
inChain[u] = cursz[Chain]++;
int nxt = 0;
for (auto v : ad[u]){
if (v == p) continue;
if (sz[v] > sz[nxt]) nxt = v;
}
if (nxt) hld(nxt, u);
for (auto v : ad[u]){
if (v == p || v == nxt) continue;
Chain++;
hld(v, u);
}
}
int update(int u, int ncat, int ndog){
st[id[u]].upd(inChain[u], ncat, ndog);
while(u){
int v = par[head[id[u]]];
if (v){
st[id[v]].upd(inChain[v], -pre[0][id[u]], -pre[1][id[u]]);
}
pre[0][id[u]] = min(st[id[u]].cat(), st[id[u]].dog() + 1);
pre[0][id[u]] = min(st[id[u]].dog(), st[id[u]].cat() + 1);
if (v){
st[id[v]].upd(inChain[v], pre[0][id[u]], pre[1][id[u]]);
}
u = par[head[id[u]]];
}
return min(st[1].dog(), st[1].cat());
}
void initialize(int N, vector<int> A, vector<int> B){
n = N;
for(int i = 0; i < n - 1; i++){
ad[A[i]].push_back(B[i]);
ad[B[i]].push_back(A[i]);
}
dfs(1, -1);
Chain = 1, timeDfs = 0;
hld(1, -1);
for(int i = 1; i <= Chain; i++) st[i] = Segtree(cursz[i]);
}
int cat (int u){
type[u] = 1;
return update(u, 0, maxn);
}
int dog(int u){
type[u] = 2;
return update(u, maxn, 0);
}
int neighbor(int u){
int val = type[u];
type[u] = 0;
return (val == 1 ? update(u, 0, - n) : update(u, -n, 0));
}
