#include "catdog.h"
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
using namespace std;
const int Nmax = 1e5 + 5, inf = 1e6;
int n, tip[Nmax];
class SegmentTree
{
int *go[2][2];
public:
void build(int nr)
{
int i, j;
for(i=0; i<2; ++i)
for(j=0; j<2; ++j)
go[i][j] = new int [nr << 2];
}
void build(int node, int st, int dr)
{
if(st == dr)
{
go[0][0][node] = go[1][1][node] = 0;
go[0][1][node] = go[1][0][node] = inf;
return;
}
build(left_son, st, mid);
build(right_son, mid+1, dr);
go[0][0][node] = go[1][1][node] = 0;
go[0][1][node] = go[1][0][node] = 1;
}
void update(int node, int st, int dr, int pos, int a1, int a2)
{
if(st == dr)
{
go[0][0][node] += a1;
go[1][1][node] += a2;
return;
}
if(pos <= mid) update(left_son, st, mid, pos, a1, a2);
else update(right_son, mid+1, dr, pos, a1, a2);
int i, j, k, t;
for(i=0; i<2; ++i)
for(j=0; j<2; ++j)
{
int x = 10 * inf;
for(k=0; k<2; ++k)
for(t=0; t<2; ++t)
x = min(x, go[i][k][left_son] + go[t][j][right_son] + (k != t));
go[i][j][node] = x;
}
}
int query0()
{
return min(go[0][0][1], go[0][1][1]);
}
int query1()
{
return min(go[1][0][1], go[1][1][1]);
}
int query()
{
return min(query1(), query0());
}
} aint[Nmax];
namespace hp
{
vector<int> v[Nmax], chain[Nmax];
int nr = 0;
int w[Nmax], t[Nmax], pos[Nmax], where[Nmax];
void dfs(int node, int dad = 0)
{
w[node] = 1; t[node] = dad;
for(auto it : v[node])
if(it != dad)
{
w[node] += w[it];
dfs(it, node);
}
}
void make_chains(int node)
{
where[node] = nr;
pos[node] = chain[nr].size();
chain[nr].push_back(node);
int xson = -1;
for(auto it : v[node])
if(it != t[node] && (xson == -1 || w[xson] < w[it])) xson = it;
if(xson == -1) return;
make_chains(xson);
for(auto it : v[node])
if(it != t[node] && it != xson)
{
++nr;
make_chains(it);
}
}
void prepare()
{
dfs(1);
nr = 1; make_chains(1);
int i;
for(i=1; i<=nr; ++i)
{
aint[i].build(chain[i].size());
aint[i].build(1, 0, chain[i].size() - 1);
}
}
void update(int node, int add1, int add2)
{
int T, ans0, ans1;
int C = where[node];
T = t[chain[C][0]];
if(T)
ans0 = aint[C].query0(), ans1 = aint[C].query1();
aint[C].update(1, 0, chain[C].size() - 1, pos[node], add1, add2);
if(!T) return;
int ans2, ans3;
ans2 = aint[C].query0();
ans3 = aint[C].query1();
update(T, min(ans2, ans3 + 1) - min(ans0, ans1 + 1), min(ans2 + 1, ans3) - min(ans0 + 1, ans1));
}
}
void initialize(int N, vector<int> A, vector<int> B)
{
int i;
n = N;
for(i=0; i<n-1; ++i)
{
hp :: v[A[i]].push_back(B[i]);
hp :: v[B[i]].push_back(A[i]);
}
hp :: prepare();
}
int cat(int v) /// tip 1
{
hp :: update(v, 0, inf);
tip[v] = 1;
return aint[1].query();
}
int dog(int v) /// tip 2
{
hp :: update(v, inf, 0);
tip[v] = 2;
return aint[1].query();
}
int neighbor(int v) /// tip 0
{
if(tip[v] == 1) hp :: update(v, 0, -inf);
else hp :: update(v, -inf, 0);
tip[v] = 0;
return aint[1].query();
}
