#include "catdog.h"
#include <algorithm>
using namespace std;
int N;
vector<int> G[100100]; int P[100100];
const int inf = 1000000000;
struct mat{
mat(long long a, long long b)
{
if (a > inf) a = inf;
if (b > inf) b = inf;
A[0][0] = a; A[0][1] = a+1;
A[1][0] = b+1; A[1][1] = b;
}
mat()
{
A[0][0] = 0; A[0][1] = 1;
A[1][0] = 1; A[1][1] = 0;
}
int A[2][2];
mat operator *(const mat &t) const{
mat r(0,0);
for (int i=0;i<2;i++) for (int j=0;j<2;j++){
r.A[i][j] = inf;
for (int k=0;k<2;k++){
r.A[i][j] = min(r.A[i][j],A[i][k]+t.A[k][j]);
}
}
return r;
};
};
vector<int> see;
int go(int x, int l)
{
see.push_back(x);
P[x] = l;
auto I = find(G[x].begin(),G[x].end(),l);
if (I != G[x].end()) G[x].erase(I);
int sz = 1, mx = 0, v;
for (auto &y : G[x]){
int z = go(y,x);
sz += z;
if (mx < z)
mx = z, v = y;
}
if (mx){
auto J = find(G[x].begin(),G[x].end(),v);
swap(G[x][0],*J);
}
return sz;
}
int C,num[100100],pos[100100],sz[100100],pw[100100],la[100100],lb[100100];
vector<long long> chain[100100],addA[100100],addB[100100];
vector<mat> IT[100100];
void initialize(int N_, std::vector<int> A, std::vector<int> B) {
N = N_;
for (int i=0;i<A.size();i++){
int x = A[i], y = B[i];
G[x].push_back(y);
G[y].push_back(x);
}
go(1,0);
C++;
for (int &i : see){
if (G[i].empty()) continue;
int x = G[i][0];
num[x] = num[i];
for (int j=1;j<G[i].size();j++){
int y = G[i][j];
num[y] = C++;
}
}
for (int &i : see){
pos[i] = sz[num[i]]++;
chain[num[i]].push_back(i);
}
for (int i=0;i<C;i++){
addA[i].resize(sz[i]);
addB[i].resize(sz[i]);
pw[i] = 1;
while (pw[i] < sz[i]) pw[i] *= 2;
IT[i].resize(pw[i]*2);
}
}
void up(vector<mat> &it, int Z, int x, mat t)
{
x += Z;
it[x] = t; x /= 2;
while (x){
it[x] = it[x*2] * it[x*2+1];
x /= 2;
}
}
void push(int x, int a, int b)
{
bool f = true;
while (x){
int n = num[x];
int v = chain[n][0];
int p = P[v];
if (p){
int A = min(IT[n][1].A[0][0],IT[n][1].A[0][1]);
int B = min(IT[n][1].A[1][0],IT[n][1].A[1][1]);
int np = num[p];
addA[np][pos[p]] -= min(A,B+1);
addB[np][pos[p]] -= min(A+1,B);
}
int ps = pos[x];
if (f){
addA[n][ps] -= la[x];
addB[n][ps] -= lb[x];
la[x] = a;
lb[x] = b;
addA[n][ps] += a;
addB[n][ps] += b;
f = 0;
}
up(IT[n], pw[n], ps, mat(addA[n][ps],addB[n][ps]));
if (p){
int A = min(IT[n][1].A[0][0],IT[n][1].A[0][1]);
int B = min(IT[n][1].A[1][0],IT[n][1].A[1][1]);
int np = num[p];
addA[np][pos[p]] += min(A,B+1);
addB[np][pos[p]] += min(A+1,B);
}
x = p;
}
}
int getV()
{
return min({IT[0][1].A[0][0],IT[0][1].A[0][1],IT[0][1].A[1][0],IT[0][1].A[1][1]});
}
int cat(int v) {
push(v, 0, inf);
return getV();
}
int dog(int v) {
push(v, inf ,0);
return getV();
}
int neighbor(int v) {
push(v, 0, 0);
return getV();
}
