#include "catdog.h"
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 100000, N_ = 1 << 17, INF = 0x3f3f3f3f; /* N_ = pow2(ceil(log2(N))) */
int min(int a, int b) { return a < b ? a : b; }
int *ej[N], eo[N], n;
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int dd[N], pp[N], qq[N], tt[N], ta[N], tb[N];
int dfs1(int p, int i, int d) {
pp[i] = p, dd[i] = d;
int s = 1, k_ = 0, j_ = -1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
int k = dfs1(i, j, d + 1);
s += k;
if (k_ < k)
k_ = k, j_ = j;
}
}
qq[i] = j_;
tt[i] = j_ == -1 ? i : tt[j_];
return s;
}
void dfs2(int p, int i, int q) {
static int time;
ta[i] = time++;
int j_ = qq[i]; qq[i] = q;
if (j_ != -1)
dfs2(i, j_, q);
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && j != j_)
dfs2(i, j, j);
}
tb[i] = time;
}
int st[N_ * 2][2][2], n_;
void combine(int aa[][2], int bb[][2], int cc[][2]) {
static int tt[2][2];
memset(tt, 0x3f, sizeof tt);
for (int u = 0; u < 2; u++)
for (int v = 0; v < 2; v++)
for (int w = 0; w < 2; w++)
tt[u][w] = min(tt[u][w], aa[u][v] + bb[v][w]);
memcpy(cc, tt, sizeof tt);
}
void pul(int i) {
combine(st[i << 1 | 0], st[i << 1 | 1], st[i]);
}
void update(int i, int x0, int x1) {
i += n_;
st[i][0][0] = x0, st[i][0][1] = x1 == INF ? INF : x1 + 1;
st[i][1][0] = x0 == INF ? INF : x0 + 1, st[i][1][1] = x1;
while (i > 1)
pul(i >>= 1);
}
void query(int l, int r, int *x0, int *x1) {
static int dp[2][2], dq[2][2];
for (int u = 0; u < 2; u++)
for (int v = 0; v < 2; v++)
dp[u][v] = dq[u][v] = u == v ? 0 : INF;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
combine(dp, st[l++], dp);
if ((r & 1) == 0)
combine(st[r--], dq, dq);
}
combine(dp, dq, dp);
*x0 = min(dp[0][0], dp[0][1]), *x1 = min(dp[1][0], dp[1][1]);
}
void build(int n) {
n_ = 1;
while (n_ < n)
n_ <<= 1;
for (int i = 0; i < n; i++) {
st[n_ + i][0][0] = 0, st[n_ + i][0][1] = 1;
st[n_ + i][1][0] = 1, st[n_ + i][1][1] = 0;
}
for (int i = n_ - 1; i > 0; i--)
pul(i);
}
int cc[N], dp0[N], dp1[N];
void initialize(int n, vi ii, vi jj) {
n = ii.size() + 1;
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (int h = 0; h < n - 1; h++) {
int i = ii[h] - 1, j = jj[h] - 1;
append(i, j), append(j, i);
}
dfs1(-1, 0, 0);
dfs2(-1, 0, 0);
memset(cc, -1, n * sizeof *cc);
build(n);
}
int update_(int i, int c) {
cc[i] = c;
while (1) {
int q = qq[i], p = pp[qq[i]], x0, x1;
if (p != -1) {
query(ta[q], ta[tt[q]], &x0, &x1);
dp0[p] -= x0, dp1[p] -= x1;
}
if (cc[i] == 0)
update(ta[i], dp0[i], INF);
else if (cc[i] == 1)
update(ta[i], INF, dp1[i]);
else
update(ta[i], dp0[i], dp1[i]);
query(ta[q], ta[tt[q]], &x0, &x1);
if (p != -1) {
dp0[p] += x0, dp1[p] += x1;
i = p;
} else
return min(x0, x1);
}
}
int cat(int i) {
i--;
return update_(i, 0);
}
int dog(int i) {
i--;
return update_(i, 1);
}
int neighbor(int i) {
i--;
return update_(i, -1);
}
