#include "catdog.h"
#include <algorithm>
#include <functional>
using namespace std;
typedef pair<int, int> pii;
typedef long long llong;
const llong inf = 1e16;
const int MAXN = 1e6;
struct node {
llong val[2][2];
node() {
val[0][0] = val[1][1] = 0;
val[0][1] = val[1][0] = inf;
}
node operator+(const node &p) const {
node ret;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
ret.val[i][j] = inf;
for (int k = 0; k < 2; ++k) {
for (int l = 0; l < 2; ++l) {
ret.val[i][j] = min(ret.val[i][j]
, val[i][k] + p.val[l][j] + (k ^ l));
}
}
}
}
return ret;
}
};
struct segtree {
vector<node> val;
int sz;
void init(int i, int s, int e) {
if (s == e) return;
int m = (s + e) / 2;
init(i << 1, s, m);
init(i << 1 | 1, m + 1, e);
val[i] = val[i << 1] + val[i << 1 | 1];
}
void init(int _sz) {
int s = 1;
sz = _sz;
while (s < (sz << 1)) s <<= 1;
val.resize(s);
init(1, 1, sz);
}
void update(int i, int s, int e, int x, llong v0, llong v1) {
if (s == e) {
val[i].val[0][0] += v0;
val[i].val[1][1] += v1;
return;
}
int m = (s + e) / 2;
if (x <= m) update(i << 1, s, m, x, v0, v1);
else update(i << 1 | 1, m + 1, e, x, v0, v1);
val[i] = val[i << 1] + val[i << 1 | 1];
}
void update(int i, llong x0, llong x1) {
update(1, 1, sz, i, x0, x1);
}
pii query() const {
int x = min(val[1].val[0][0], val[1].val[0][1]);
int y = min(val[1].val[1][0], val[1].val[1][1]);
return pii(min(x, y + 1), min(x + 1, y));
}
} seg[100001];
int n;
vector<int> edge[100001];
int sz[100001];
int pathPar[100001];
int pathPos[100001];
int par[100001];
int st[100001];
void dfsSize(int x, int p) {
par[x] = p;
sz[x] = 1;
for (int i : edge[x]) {
if (i == p) continue;
dfsSize(i, x);
sz[x] += sz[i];
}
}
void dfsDecomp(int x, int p) {
int hpath = 0;
for (int i : edge[x]) {
if (i == p) continue;
if (sz[x] <= (sz[i] << 1)) {
hpath = i;
break;
}
}
if (hpath == 0) seg[pathPar[x]].init(pathPos[x]);
for (int i : edge[x]) {
if (i == p) continue;
if (i != hpath) {
pathPar[i] = i;
pathPos[i] = 1;
}
else {
pathPar[i] = pathPar[x];
pathPos[i] = pathPos[x] + 1;
}
dfsDecomp(i, x);
}
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for (int i = 0; i < n - 1; ++i) {
edge[A[i]].push_back(B[i]);
edge[B[i]].push_back(A[i]);
}
dfsSize(1, 0);
pathPar[1] = 1;
pathPos[1] = 1;
dfsDecomp(1, 0);
}
void update(int x, int v0, int v1) {
while (x) {
int path = pathPar[x];
int pr0, pr1, nx0, nx1;
tie(pr0, pr1) = seg[path].query();
seg[path].update(pathPos[x], v0, v1);
tie(nx0, nx1) = seg[path].query();
v0 = nx0 - pr0;
v1 = nx1 - pr1;
x = par[pathPar[x]];
}
}
int getAns() {
int x, y;
tie(x, y) = seg[1].query();
return min(x, y);
}
int cat(int v) {
st[v] = 1;
update(v, MAXN, 0);
return getAns();
}
int dog(int v) {
st[v] = 2;
update(v, 0, MAXN);
return getAns();
}
int neighbor(int v) {
if (st[v] == 1) update(v, -MAXN, 0);
else update(v, 0, -MAXN);
st[v] = 0;
return getAns();
}
