#include "catdog.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ll long long int
#define SIZE 100005
#define all(v) v.begin(), v.end()
#define pb push_back
#define MOD 1000000007
#define INF 1000000007
using namespace std;
int n;
vector<int> g[SIZE] , child[SIZE];
int C[SIZE];
int sz[SIZE] , dep[SIZE] , pa[SIZE];
int num[SIZE] , TOP[SIZE] , BOT[SIZE];
int L[SIZE][2];
struct ST{
struct Node {
int v[2][2] , e;
int getmin() const { return min(min(v[0][0] , v[0][1]) , min(v[1][0] , v[1][1])); }
Node operator+(const Node& b) {
if (e==1) return b;
if (b.e==1) return {v[0][0] , v[0][1] , v[1][0] , v[1][1] , e};
Node val={INF , INF , INF , INF , 0};
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) for (int l = 0; l < 2; l++) val.v[i][l] = min(val.v[i][l] , v[i][j]+b.v[k][l]+(j!=k));
return val;
}
};
Node tree[SIZE*4];
//build
void build(int nod , int nl , int nr) {
if (nl == nr) {
tree[nod] = {0 , INF , INF , 0 , 0};
return;
}
int m = (nl+nr)/2;
build(nod*2 , nl , m); build(nod*2+1 , m+1 , nr);
tree[nod] = tree[nod*2]+tree[nod*2+1];
}
//query
Node query(int nod , int nl , int nr , int l , int r) {
if (nr < l || r < nl) return {INF , INF , INF , INF , 1};
if (l <= nl && nr <= r) return tree[nod];
int m = (nl+nr)/2;
Node Lval = query(nod*2 , nl , m , l , r);
Node Rval = query(nod*2+1 , m+1 , nr , l , r);
return Lval+Rval;
}
//update
void update(int nod , int nl , int nr , int idx , Node val) {
if (nr < idx || idx < nl) return;
if (nl == nr) { tree[nod]=val; return; }
int m = (nl+nr)/2;
update(nod*2 , nl , m , idx , val);
update(nod*2+1 , m+1 , nr , idx , val);
tree[nod] = tree[nod*2]+tree[nod*2+1];
}
pii G(Node X) {
return {min(X.v[0][0] , X.v[0][1]) , min(X.v[1][0] , X.v[1][1])};
}
void upd(int idx) {
Node ret = {INF , INF , INF , INF , 0};
if (C[idx]!=2) ret.v[0][0] = L[idx][0];
if (C[idx]!=1) ret.v[1][1] = L[idx][1];
update(1 , 1 , n , idx , ret);
}
}seg;
void bui(int here , int p) {
for (auto t : g[here]) {
if (p == t) continue;
pa[t] = here;
dep[t] = dep[here]+1;
child[here].pb(t); bui(t , here);
}
}
void getsz(int here) {
sz[here]=1;
for (auto &t : child[here]) {
getsz(t);
sz[here] += sz[t];
if (sz[t] > sz[child[here].front()]) swap(child[here].front() , t);
}
}
int pv;
void hld(int here) {
num[here] = ++pv;
bool isFirst=true;
for (auto t : child[here]) {
if (isFirst) {
TOP[t] = TOP[here];
isFirst=false;
}
else TOP[t]=t;
hld(t);
}
BOT[here] = child[here].size() > 0 ? BOT[child[here][0]] : here;
}
int solve(int idx , int x) {
C[num[idx]] = x;
while(TOP[idx]!=1) {
auto [prv0 , prv1] = seg.G(seg.query(1 , 1 , n , num[TOP[idx]] , num[BOT[idx]]));
seg.upd(num[idx]);
auto [cur0 , cur1] = seg.G(seg.query(1 , 1 , n , num[TOP[idx]] , num[BOT[idx]]));
idx = pa[TOP[idx]];
L[num[idx]][0] += min(cur0 , cur1+1)-min(prv0 , prv1+1);
L[num[idx]][1] += min(cur0+1 , cur1)-min(prv0+1 , prv1);
}
seg.upd(num[idx]);
return seg.query(1 , 1 , n , num[TOP[idx]] , num[BOT[idx]]).getmin();
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for (int i = 0; i < A.size(); i++) {
g[A[i]].pb(B[i]); g[B[i]].pb(A[i]);
}
bui(1,-1);
getsz(1);
TOP[1]=1;
hld(1);
seg.build(1 , 1 , n);
}
int cat(int v) {
return solve(v , 1);
}
int dog(int v) {
return solve(v , 2);
}
int neighbor(int v) {
return solve(v , 3);
}
