#include<bits/stdc++.h>
#include "catdog.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define INF 100010
#define MOD 1000000007
#define all(x) x.begin(), x.end()
struct nda{
int cc = 0, cd = INF;
int dc = INF, dd = 0;
bool eq(nda v){
return (cc == v.cc) && (cd == v.cd) &&
(dc == v.dc) && (dd == v.dd);
}
};
nda mu(nda a, nda b){
if(a.eq({-1,-1,-1,-1})) return b;
if(b.eq({-1,-1,-1,-1})) return a;
nda ans;
ans.cc = min({a.cc+b.cc, a.cc+b.dc+1, a.cd+b.cc+1, a.cd+b.dc});
ans.cd = min({a.cc+b.cd, a.cc+b.dd+1, a.cd+b.cd+1, a.cd+b.dd});
ans.dc = min({a.dc+b.cc, a.dc+b.dc+1, a.dd+b.cc+1, a.dd+b.dc});
ans.dd = min({a.dc+b.cd, a.dc+b.dd+1, a.dd+b.cd+1, a.dd+b.dd});
return ans;
}
class SegTree{
vector<nda> st; int l, r;
void Update(int node, int l, int r, int L, int R, int v0, int v1){
if(r < L or R < l) return;
if(L <= l and r <= R){
st[node].cc += v0;
st[node].dd += v1;
return;
}
int m = (l+r)>>1;
Update(node*2, l, m, L, R, v0, v1);
Update(node*2+1, m+1, r, L, R, v0, v1);
st[node] = mu(st[node*2], st[node*2+1]);
return;
}
nda Query(int node, int l, int r, int L, int R){
if(r < L or R < l) return nda{-1,-1,-1,-1};
if(L <= l and r <= R) return st[node];
int m = (l+r)>>1;
auto v1 = Query(node*2, l, m, L, R);
auto v2 = Query(node*2+1, m+1, r, L, R);
return mu(v1, v2);
}
public:
SegTree(int l, int r){
int sz = (r-l+1);
st.resize(4*sz);
this->l = l, this->r = r;
}
void Update(int L, int R, int v0, int v1){
Update(1, l, r, L, R, v0, v1);
return;
}
nda Query(int L, int R){
return Query(1, l, r, L, R);
}
};
class HLD{
vi heavy, head, pos; // [next node, root of chain, index]
vi parent, depth;
int pos_timer = 0;
SegTree ST;
vi ende;
int dfs(int u, const vvi &adj){
int subtree_size = 1, max_size = 0;
for(auto v : adj[u]){
if(v == parent[u]) continue;
parent[v] = u, depth[v] = depth[u]+1;
int child_subtree_size = dfs(v, adj);
subtree_size += child_subtree_size;
if(max_size < child_subtree_size){
max_size = child_subtree_size;
heavy[u] = v;
}
}
return subtree_size;
}
void decompose(int u, int h, const vvi &adj){
head[u] = h; pos[u] = pos_timer++;
ende[h] = pos[u];
if(heavy[u] != -1)
decompose(heavy[u], h, adj);
for(auto v : adj[u]){
if(v == parent[u] || v == heavy[u]) continue;
decompose(v, v, adj);
}
return;
}
public:
HLD(const vvi &adj) : ST(0, adj.size()-1){
int N = adj.size(); // !!0 based indexing!!
heavy = vi(N, -1), head = vi(N), pos = vi(N);
parent = vi(N), depth = vi(N);
ende = vi(N);
dfs(0, adj);
decompose(0, 0, adj);
}
int Update(int a, int v0, int v1){
for(int u = a; true; u = parent[head[u]]){
auto prev = ST.Query(pos[head[u]], ende[head[u]]);
ST.Update(pos[u], pos[u], v0, v1);
auto next = ST.Query(pos[head[u]], ende[head[u]]);
v0 = min({next.cc, next.cd, next.dc+1, next.dd+1}) -
min({prev.cc, prev.cd, prev.dc+1, prev.dd+1});
v1 = min({next.dd, next.dc, next.cc+1, next.cd+1}) -
min({prev.dd, prev.dc, prev.cc+1, prev.cd+1});
if(head[u] == 0){
return min({next.cc, next.cd, next.dc, next.dd});
}
}
return -1; // impossible case
}
};
vi col; HLD hvt(vvi(1));
void initialize(int n, vi a, vi b){
vvi adj(n); col = vi(n, 0);
for(int x = 0; x < n-1; x++){
adj[a[x]-1].push_back(b[x]-1);
adj[b[x]-1].push_back(a[x]-1);
}
hvt = HLD(adj);
return;
}
// cat ==> 0
int cat(int v){
v--; col[v] = 1;
return hvt.Update(v, 0, INF);
}
// dog ==> 1
int dog(int v){
v--; col[v] = 2;
return hvt.Update(v, INF, 0);
}
int neighbor(int v){
v--; int tp = col[v]; col[v] = 0;
if(tp == 1) return hvt.Update(v, 0, -INF);
return hvt.Update(v, -INF, 0);
}
