#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const ll inf = 1e16;
const int MAXN = 1e6 + 5, MAXNN = 1e5 + 5;
struct node {
ll 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 root, int lo, int hi){
if(lo == hi) return;
int mid = (lo + hi)>>1, left = root<<1, right = left | 1;
init(left, lo, mid);
init(right, mid + 1, hi);
val[root] = val[left] + val[right];
}
void init(int n){
int s = 1;
sz = n;
while(s < (sz << 1)) s <<= 1;
val.resize(s);
init(1, 1, sz);
}
void update(int root, int lo, int hi, int x, ll v0, ll v1){
if(lo == hi){
val[root].val[0][0] += v0;
val[root].val[1][1] += v1;
return;
}
int mid = (lo + hi)>>1, left = root<<1, right = left | 1;
if(x <= mid) update(left, lo, mid, x, v0, v1);
else update(right, mid + 1, hi, x, v0, v1);
val[root] = val[left] + val[right];
}
void update(int pos, ll x0, ll x1){
update(1, 1, sz, pos, 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[MAXNN];
int n;
vector<int> edge[MAXNN];
int sz[MAXNN], pathPar[MAXNN], pathPos[MAXNN], par[MAXNN], st[MAXNN];
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(){
pii it = seg[1].query();
return min(it.first, it.second);
}
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();
}
