#include "catdog.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
struct F {
int mat[2][2] = {{0,1},{1,0}};
friend F op(const F& u,const F& v) {
F res = {oo,oo,oo,oo};
for(int i : {0,1}) for(int j : {0,1}) for(int k : {0,1}) {
res.mat[i][k] = min(res.mat[i][k], u.mat[i][j]+v.mat[j][k]);
}
return res;
}
int get() {
int ans=oo;
for(int i : {0,1}) for(int j : {0,1}) ans = min(ans,mat[i][j]);
return ans;
}
pair<ll,ll> dp() {
int x=oo,y=oo;
for(int i : {0,1}) {
x = min(x,mat[i][0]);
y = min(y,mat[i][1]);
}
return {x,y};
}
};
template<class T> struct splaytree {
// flip
#define L c[0]
#define R c[1]
struct node {
T val;
node *c[2] = {NULL,NULL}, *par =NULL;
bool pathtop=true;
node(const T& v) : val(v) {}
node() {}
};
static void recalc(node* at) {
at->val.recalc();
if(at->L) at->val.recalc(at->L->val,0);
if(at->R) at->val.recalc(at->R->val,1);
}
static void print(node* n) {
if(n==NULL) return;
print(n->L);
cout << n->val << ' ';
print(n->R);
}
static void rotate(node* n) {
// Precondition: n is not the root, Postcondition: rotates n to the place of its parent
assert(n and !n->pathtop and n->par);
node* par = n->par;
if(!par->pathtop) {
auto gp = par->par;
if(gp->L==par) gp->L=n;
else if(gp->R==par) gp->R=n;
}
n->par = par->par;
bool b= n!=par->L;
#define l c[b]
#define r c[b^1]
par->l = n->r; // Fix right child of current node
if(n->r) n->r->par = par;
n->r = par; // Put parent under current node
#undef l
#undef r
par->par = n;
swap(par->pathtop, n->pathtop);
recalc(par), recalc(n);
}
static void splay(node* n) {
while(!n->pathtop) {
if(n->par->pathtop) {
rotate(n);
} else {
auto p = n->par, gp = p->par;
// Double rotations
if((p->L==n) == (gp->L==p)) rotate(p);
else rotate(n);
rotate(n);
}
}
}
#undef L
#undef R
};
struct vertex{
F mine,sub;
vertex(){}
void recalc(const vertex& o,bool rev=false) {
sub = rev?op(o.sub,sub):op(sub,o.sub);
}
void recalc() {
sub=mine;
}
};
array<array<ll,2>,2> matSingle[3] = {{0,1,1,0}, {0,oo,1,oo}, {oo,1,oo,0}};
struct linkcut {
// initially the linkcut tree consists of n disconnected size 1 trees.
typedef splaytree<vertex> bst;
typedef bst::node node;
int n=0;
node* t=NULL;
linkcut() {}
linkcut(int nn) {
n=nn;
t = new node[n];
for(int i=0;i<n;++i) {
t[i] = node(vertex{});
}
}
void attach(node* at, int sgn=1) {
auto& f = at->par->val.mine;
auto [x,y] = at->val.sub.dp();
f.mat[0][1]+=sgn*min(x+1,y);
f.mat[1][1]+=sgn*min(x+1,y);
f.mat[0][0]+=sgn*min(x,y+1);
f.mat[1][0]+=sgn*min(x,y+1);
}
void attach(int i, int sgn=1) {
attach(t+i,sgn);
}
node* expose(int u) {
node *at = NULL, *par = t+u;
for(;par; at=par,par = par->par) {
bst::splay(par);
if(par->c[1]) {
attach(par->c[1]);
par->c[1]->pathtop = true;
par->c[1] = NULL;
}
if(at) {
attach(at,-1);
at->pathtop = false;
}
par->c[1] = at;
bst::recalc(par);
}
bst::splay(t+u);
return t+u;
}
void link(int u, int v) { // precondition: u is root of tree
t[u].par = t+v; // connect with unmarked edge
attach(u);
}
ll calc() {
auto root = expose(0);
return root->val.sub.get();
}
void update(int i, int old, int nw) {
expose(i);
for(int j=0;j<2;++j) for(int k=0;k<2;++k) {
t[i].val.mine.mat[j][k]+=matSingle[nw][j][k]-matSingle[old][j][k];
}
bst::recalc(t+i);
}
};
vvi adj;
linkcut tree;
void dfs(int at, int from) {
for(int to : adj[at]) if(to!=from) {
dfs(to,at);
tree.link(to,at);
}
}
int n;
vi typ;
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n=N;
adj.resize(n);
for(int i=0;i<n-1;++i) {
adj[A[i]-1].push_back(B[i]-1);
adj[B[i]-1].push_back(A[i]-1);
}
tree = linkcut(n);
typ.resize(n);
dfs(0,0);
}
int update(int v, int a) {
tree.update(v,typ[v],a);
typ[v]=a;
return tree.calc();
}
int cat(int v) {
return update(v-1,2);
}
int dog(int v) {
return update(v-1,1);
}
int neighbor(int v) {
return update(v-1,0);
}
