#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
template<typename T> struct AINT{
vector<T> aint; int n;
void init(int _n){n=_n;aint.assign(2*n+5,T());}
template<class CB> void walk(CB&& cb){walk(cb,1,n);}
template<class CB> void walk(CB&& cb, int l, int r){walk(cb,l,r,1,1,n);}
template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr){
if(cr < l || r < cl) return;
if(l <= cl && cr <= r && !cb(aint[node],cl,cr)) return;
int mid = (cl+cr)>>1, L = node+1, R = node + (mid-cl+1)*2;
walk(cb,l,r,L,cl,mid); walk(cb,l,r,R,mid+1,cr);
aint[node].pull(aint[L],aint[R]);
}
};
struct Node{
array<array<int,2>,2> dp;
Node(){dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=0;}
int& operator()(int i, int j){return dp[i][j];}
void pull(Node a, Node b){
dp[0][0] = min({a(0,0)+b(0,0),a(0,1)+b(1,0),a(0,0)+b(1,0)+1,a(0,1)+b(0,0)+1});
dp[0][1] = min({a(0,0)+b(0,1),a(0,1)+b(1,1),a(0,0)+b(1,1)+1,a(0,1)+b(0,1)+1});
dp[1][0] = min({a(1,0)+b(0,0),a(1,1)+b(1,0),a(1,0)+b(1,0)+1,a(1,1)+b(0,0)+1});
dp[1][1] = min({a(1,0)+b(0,1),a(1,1)+b(1,1),a(1,0)+b(1,1)+1,a(1,1)+b(0,1)+1});
}
}id;
Node operator+(Node a,Node b){
Node res; res.pull(a,b);
return res;
}
const int mxn = 1e5+1, inf = 1e8;
vector<int> g[mxn];
int par[mxn],head[mxn],tin[mxn],tout[mxn];
int heavy[mxn],cur_pos=0;
AINT<Node> segtree[mxn];
char col[mxn];
int dp[mxn][2];
void upd_node(int u){
segtree[head[u]].walk([&](Node &val, int l, int r){
val(0,0) = dp[u][0];
val(1,1) = dp[u][1];
if(col[u]!=-1)
val(1-col[u],1-col[u]) = inf;
return 0;
},tin[u],tin[u]);
}
int pre_dfs(int u = 1, int p = 0){
int sz = 1, mx = 0; par[u]=p;
for(auto v : g[u]) if(v!=p){
int vsz = pre_dfs(v,u);
sz += vsz;
if(mx < vsz)
heavy[u] = v, mx = vsz;
}
return sz;
}
void decompose(int u=1, int h=1){
if(u==h) tin[u] = 1;
else tin[u] = tin[par[u]]+1;
head[u] = h, tout[h]=tin[u];
if(heavy[u]) decompose(heavy[u],h);
dp[u][0] = dp[u][1] = 0;
for(auto v : g[u]) if(v!=par[u]&&v!=heavy[u])
decompose(v,v);
if(u==h) segtree[u].init(tout[u]-tin[u]+1);
}
void decompose2(int u=1, int h=1){
if(heavy[u]) decompose2(heavy[u]);
for(auto v : g[u]) if(v!=par[u]&&v!=heavy[u])
decompose2(v,v);
segtree[head[u]].walk([&](Node &val, int l, int r){
val(0,0) = val(1,1) = 0;
val(0,1) = val(1,0) = inf;
return 0;
},tin[u],tin[u]);
}
int update(int v, int x){
int u = head[v];
vector<int> vec;
for(; u!=1; u=head[par[u]]){
vec.emplace_back(u);
}
for(; !vec.empty(); vec.pop_back()){
u = vec.back();
auto val = segtree[u].aint[1];
int a = min(val(0,0),val(0,1));
int b = min(val(1,0),val(1,1));
dp[par[u]][0] -= min(a,b+1);
dp[par[u]][1] -= min(a+1,b);
upd_node(par[u]);
}
col[v] = x; upd_node(v);
u = head[v];
for(; u!=1; u=head[par[u]]){
auto val = segtree[u].aint[1];
int a = min(val(0,0),val(0,1));
int b = min(val(1,0),val(1,1));
dp[par[u]][0] += min(a,b+1);
dp[par[u]][1] += min(a+1,b);
upd_node(par[u]);
}
auto val = segtree[1].aint[1];
return min({val(0,0),val(0,1),val(1,0),val(1,1)});
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
for(int i = 0; i < N-1; i++){
g[A[i]].emplace_back(B[i]);
g[B[i]].emplace_back(A[i]);
}
pre_dfs(); decompose();
decompose2();
fill(col+1,col+N+1,-1);
}
int cat(int v) {
return update(v,0);
}
int dog(int v) {
return update(v,1);
}
int neighbor(int v) {
return update(v,-1);
}
