// #include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 100000;
int n, m, u, v, add[2], sub[2], color[100005], f[100005][2], _g[100005][2];
int cnt, fa[100005], siz[100005], dep[100005], son[100005], dfn[100005], top[100005], rnk[100005], bot[100005];
vector<int> e[100005];
struct matrix {
int v[2][2];
matrix(int val = inf) {
v[0][0] = val, v[0][1] = inf;
v[1][0] = inf, v[1][1] = val;
}
matrix operator = (const matrix& _) {
v[0][0] = _.v[0][0], v[0][1] = _.v[0][1];
v[1][0] = _.v[1][0], v[1][1] = _.v[1][1];
return *this;
}
matrix operator * (const matrix& _) const {
matrix ret;
ret.v[0][0] = min(v[0][0] + _.v[0][0], v[0][1] + _.v[1][0]);
ret.v[0][1] = min(v[0][0] + _.v[0][1], v[0][1] + _.v[1][1]);
ret.v[1][0] = min(v[1][0] + _.v[0][0], v[1][1] + _.v[1][0]);
ret.v[1][1] = min(v[1][0] + _.v[0][1], v[1][1] + _.v[1][1]);
return ret;//循环展开后的广义矩阵乘法
}
} ans, before, after, g[100005];
struct Segment_Tree {//线段树维护转移矩阵
matrix val[400005];
int pos, L, R, l[400005], r[400005];
#define lc (k << 1)
#define rc ((k << 1) | 1)
#define mid ((l[k] + r[k]) >> 1)
void push_up(int k) {
val[k] = val[lc] * val[rc];
}
void build(int k) {
if(l[k] == r[k]) {
val[k] = g[rnk[l[k]]];
return;
}
l[lc] = l[k], r[lc] = mid, l[rc] = mid + 1, r[rc] = r[k];
build(lc), build(rc);
push_up(k);
}
void change(int k) {
if(l[k] == r[k]) {
val[k] = g[rnk[pos]];
return;
}
if(pos <= mid) change(lc);
else change(rc);
push_up(k);
}
matrix ask(int k) {
if(L <= l[k] && r[k] <= R) return val[k];
matrix ret(0);
if(L <= mid) ret = ret * ask(lc);
if(R > mid) ret = ret * ask(rc);
return ret;
}
void Change(int Pos) {
pos = Pos;
return change(1);
}
matrix Ask(int l, int r) {
L = l, R = r;
return ask(1);
}
} tree;
//树链剖分
void dfs1(int now) {
siz[now] = 1, dep[now] = dep[fa[now]] + 1;
for(const auto& i : e[now]) {
if(i != fa[now]) {
fa[i] = now;
dfs1(i);
siz[now] += siz[i];
if(siz[i] > siz[son[now]]) son[now] = i;
}
}
}
void dfs2(int now) {
++cnt; dfn[now] = cnt, rnk[cnt] = now;
if(now == son[fa[now]]) top[now] = top[fa[now]];
else top[now] = now;
if(son[now]) {
dfs2(son[now]);
bot[now] = bot[son[now]];
f[now][0] += min(f[son[now]][0], f[son[now]][1] + 1);
f[now][1] += min(f[son[now]][0] + 1, f[son[now]][1]);
}
else bot[now] = now;
for(const auto& i : e[now]) {
if(i != fa[now] && i != son[now]) {
dfs2(i);
f[now][0] += min(f[i][0], f[i][1] + 1);
f[now][1] += min(f[i][0] + 1, f[i][1]);
_g[now][0] += min(f[i][0], f[i][1] + 1);
_g[now][1] += min(f[i][0] + 1, f[i][1]);
}
}
g[now].v[0][0] = _g[now][0], g[now].v[0][1] = _g[now][0] + 1;
g[now].v[1][0] = _g[now][1] + 1, g[now].v[1][1] = _g[now][1];
}
//修改转移矩阵
void change(int now, int val) {
g[now].v[0][0] = _g[now][0], g[now].v[0][1] = _g[now][0] + 1;
g[now].v[1][0] = _g[now][1] + 1, g[now].v[1][1] = _g[now][1];
color[now] = val;
if(color[now]) g[now].v[color[now] - 1][0] = g[now].v[color[now] - 1][1] = inf;//把不可能出现的一行设为inf
while(now) {
before = tree.Ask(dfn[top[now]], dfn[bot[now]]);
tree.Change(dfn[now]);
after = tree.Ask(dfn[top[now]], dfn[bot[now]]);
now = fa[top[now]];
add[0] = min(after.v[0][0], after.v[0][1]), sub[0] = min(before.v[0][0], before.v[0][1]);
add[1] = min(after.v[1][0], after.v[1][1]), sub[1] = min(before.v[1][0], before.v[1][1]);
_g[now][0] += min(add[0], add[1] + 1) - min(sub[0], sub[1] + 1), _g[now][1] += min(add[0] + 1, add[1]) - min(sub[0] + 1, sub[1]);
g[now].v[0][0] = _g[now][0], g[now].v[0][1] = _g[now][0] + 1;
g[now].v[1][0] = _g[now][1] + 1, g[now].v[1][1] = _g[now][1];
if(color[now]) g[now].v[color[now] - 1][0] = g[now].v[color[now] - 1][1] = inf;//不可能出现的状态
}
}
//下面就是交互了
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for(int i = 2; i <= n; ++i) {
u = A[i - 2], v = B[i - 2];
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1);
dfs2(1);
tree.l[1] = 1, tree.r[1] = n;
tree.build(1);
}
int cat(int v) {
change(v, 1);
ans = tree.Ask(dfn[top[1]], dfn[bot[1]]);
return min(min(ans.v[0][0], ans.v[0][1]), min(ans.v[1][0], ans.v[1][1]));
}
int dog(int v) {
change(v, 2);
ans = tree.Ask(dfn[top[1]], dfn[bot[1]]);
return min(min(ans.v[0][0], ans.v[0][1]), min(ans.v[1][0], ans.v[1][1]));
}
int neighbor(int v) {
change(v, 0);
ans = tree.Ask(dfn[top[1]], dfn[bot[1]]);
return min(min(ans.v[0][0], ans.v[0][1]), min(ans.v[1][0], ans.v[1][1]));
}
