#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1.1e5;
int N;
vector<int> adj[MAXN];
int A[MAXN];
int sz[MAXN];
int par[MAXN];
void dfs_sz(int cur, int prv) {
if (prv) {
adj[cur].erase(find(adj[cur].begin(), adj[cur].end(), prv));
}
sz[cur] = 1;
par[cur] = prv;
for (int nxt : adj[cur]) {
dfs_sz(nxt, cur);
sz[cur] += sz[nxt];
}
nth_element(adj[cur].begin(), adj[cur].begin(), adj[cur].end(), [&](int i, int j) { return sz[i] > sz[j]; });
}
int heavypar[MAXN];
int num[MAXN];
int pos[MAXN];
void dfs_hld(int cur, int top) {
heavypar[cur] = top;
pos[cur] = num[top];
num[top]++;
bool isfirst = true;
for (int nxt : adj[cur]) {
dfs_hld(nxt, (isfirst ? top : nxt));
isfirst = false;
}
}
struct mat {
int a00, a01, a10, a11;
friend mat operator * (const mat& A, const mat& B) {
mat R;
R.a00 = min(A.a00 + B.a00, A.a01 + B.a10);
R.a01 = min(A.a00 + B.a01, A.a01 + B.a11);
R.a10 = min(A.a10 + B.a00, A.a11 + B.a10);
R.a11 = min(A.a10 + B.a01, A.a11 + B.a11);
return R;
}
};
struct segtree {
int s;
vector<mat> cost;
segtree() {}
segtree(int n) {
for (s = 1; s < n; s *= 2) {}
cost = vector<mat>(2*s);
for (int i = 0; i < s; i++) {
cost[i+s].a01 = cost[i+s].a10 = 1;
}
}
void update(int i, int& v0, int& v1) {
i += s;
cost[i].a00 += v0;
cost[i].a01 += v0;
cost[i].a10 += v1;
cost[i].a11 += v1;
for (i /= 2; i; i /= 2) {
cost[i] = cost[2*i] * cost[2*i+1];
}
}
void eval(int& a0, int& a1) {
a0 = min(cost[1].a00, cost[1].a01);
a1 = min(cost[1].a10, cost[1].a11);
}
} seg[MAXN];
void initialize(int n, std::vector<int> a, std::vector<int> b) {
N = n;
for (int i = 0; i < N-1; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
for (int i = 1; i <= N; i++) {
A[i] = 0;
}
dfs_sz(1, 0);
dfs_hld(1, 1);
for (int i = 1; i <= N; i++) {
assert((pos[i] == 0) == (heavypar[i] == i));
if (heavypar[i] == i) {
seg[i] = segtree(num[i]);
}
}
}
void update(int cur, int v0, int v1) {
while (cur) {
int top = heavypar[cur];
int cur0, cur1, nxt0, nxt1;
seg[top].eval(cur0, cur1);
seg[top].update(pos[cur], v0, v1);
seg[top].eval(nxt0, nxt1);
v0 = min(nxt0, nxt1+1) - min(cur0, cur1+1);
v1 = min(nxt0+1, nxt1) - min(cur0+1, cur1);
cur = par[top];
}
}
int query();
int cat(int v) {
A[v] = 1;
update(v, 0, N);
return query();
}
int dog(int v) {
A[v] = 2;
update(v, N, 0);
return query();
}
int neighbor(int v) {
if (A[v] == 1) {
update(v, 0, -N);
} else if (A[v] == 2) {
update(v, -N, 0);
} else assert(false);
A[v] = 0;
return query();
}
int query() {
int a0, a1;
seg[1].eval(a0, a1);
return min(a0, a1);
}
