#include <bits/stdc++.h>
using namespace std;
void setup()
{
#ifndef ONLINE_JUDGE
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
struct NODE
{
int val[2][2] = {{0, 0}, {0, 0}};
NODE operator+(const NODE &inp)
{
NODE res;
for (int i = 0; i < 2; ++i)
{
for (int j = 0; j < 2; ++j)
{
res.val[i][j] = min({res.val[i][j], val[i][0] + inp.val[0][j], val[i][1] + inp.val[1][j]});
}
}
return res;
}
};
struct SEGMENT_TREE
{
vector<NODE> tree;
void Init(int n)
{
tree.resize(n << 2);
for (int i = 0; i < tree.size(); ++i)
{
tree[i].val[0][1] = tree[i].val[1][0] = 1;
}
}
void Update(int ind, int l, int r, int x, int c, int d)
{
if (r < x || x < l)
{
return;
}
if (l == r)
{
tree[ind].val[0][0] += c;
tree[ind].val[0][1] += c;
tree[ind].val[1][1] += d;
tree[ind].val[1][0] += d;
return;
}
int m = (l + r) >> 1;
Update(ind << 1, l, m, x, c, d);
Update(ind << 1 | 1, m + 1, r, x, c, d);
tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
}
void GetAll(int &c, int &d)
{
c = min(tree[1].val[0][0], tree[1].val[0][1]);
d = min(tree[1].val[1][1], tree[1].val[1][0]);
c = min(c, d + 1);
d = min(d, c + 1);
}
} st[100000];
int n;
int head[100000], num[100000], id[100000], sz[100000], mode[100000], pre[100000];
vector<int> g[100000];
void DFS(int node, int par)
{
sz[node] = 1;
pre[node] = par;
for (auto &i : g[node])
{
if (i != par)
{
DFS(i, node);
sz[node] += sz[i];
}
}
}
void HLD(int node, int par, int cur)
{
int best = -1;
head[node] = cur;
id[node] = num[cur]++;
for (auto &i : g[node])
{
if (i != par && (best == -1 || sz[i] > sz[best]))
{
best = i;
}
}
for (auto &i : g[node])
{
if (i != par)
{
HLD(i, node, (i == best ? cur : i));
}
}
}
void Update(int node, int c, int d)
{
pair<int, int> temp;
while (true)
{
st[head[node]].GetAll(temp.first, temp.second);
st[head[node]].Update(1, 0, num[head[node]] - 1, id[node], c, d);
st[head[node]].GetAll(c, d);
c -= temp.first;
d -= temp.second;
if (head[node] == 0)
{
return;
}
node = pre[head[node]];
}
}
void initialize(int _n, vector<int> _a, vector<int> _b)
{
n = _n;
for (int i = 0; i < n - 1; ++i)
{
g[_a[i] - 1].push_back(_b[i] - 1);
g[_b[i] - 1].push_back(_a[i] - 1);
}
DFS(0, 0);
HLD(0, 0, 0);
for (int i = 0; i < n; ++i)
{
st[i].Init(num[i]);
}
}
int cat(int v)
{
int c, d;
mode[v - 1] = 1;
Update(v - 1, 0, 1e9);
st[0].GetAll(c, d);
return min(c, d);
}
int dog(int v)
{
int c, d;
mode[v - 1] = 2;
Update(v - 1, 1e9, 0);
st[0].GetAll(c, d);
return min(c, d);
}
int neighbor(int v)
{
int c, d;
if (mode[v - 1] == 1)
{
Update(v - 1, 0, -1e9);
}
else
{
Update(v - 1, -1e9, 0);
}
mode[v - 1] = 0;
st[0].GetAll(c, d);
return min(c, d);
}
