#include "catdog.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <iomanip>
#include <deque>
using namespace std;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define x first
#define y second
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
const long long inf = 1e16;
const int MAXN = 1000228, MAXNN = 100228;
struct node {
long long 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, long long v0, long long 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, long long x0, long long x1){
update(1, 1, sz, pos, x0, x1);
}
pair<int, int> 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 make_pair(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(auto 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]].pb(B[i]);
edge[B[i]].pb(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() {
pair<int, int> 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();
}
