#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5, inf=1e9;
int n, pa[nx], hd[nx], hv[nx], in[nx], out[nx], t, sz[nx], type[nx];
vector<int> d[nx];
struct segtree
{
struct node
{
int dp[2][2];
node() {dp[0][1]=dp[1][0]=inf, dp[0][0]=dp[1][1]=0;}
friend node operator+ (const node &lhs, const node &rhs)
{
node tmp;
tmp.dp[0][0]=tmp.dp[0][1]=tmp.dp[1][0]=tmp.dp[1][1]=inf;
for (int i=0; i<2; i++) for (int j=0; j<2; j++) for (int k=0; k<2; k++) for (int l=0; l<2; l++) tmp.dp[i][j]=min(tmp.dp[i][j], lhs.dp[i][k]+rhs.dp[l][j]+(k!=l));
return tmp;
}
} d[4*nx];
void update(int l, int r, int i, int idx, int x, int y)
{
if (idx<l||r<idx) return;
if (l==r) return d[i].dp[0][0]+=x, d[i].dp[1][1]+=y, void();
int md=(l+r)/2;
update(l, md, 2*i, idx, x, y);
update(md+1, r, 2*i+1, idx, x, y);
d[i]=d[2*i]+d[2*i+1];
}
node query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return node();
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
}
pair<int, int> getrange(int u)
{
node tmp=query(1, n, 1, in[u], out[u]);
int cat=min(tmp.dp[0][0], tmp.dp[0][1]), dog=min(tmp.dp[1][0], tmp.dp[1][1]);
return {min(cat, dog+1), min(cat+1, dog)};
}
} s;
void dfssz(int u, int p)
{
sz[u]=1;
pa[u]=p;
for (auto v:d[u]) if (v!=p) dfssz(v, u), sz[u]+=sz[v], hv[u]=(sz[hv[u]]>sz[v])?hv[u]:v;
}
void hld(int u, int p, int g)
{
hd[u]=g;
in[u]=++t;
out[g]=t;
if (hv[u]) hld(hv[u], u, g);
for (auto v:d[u]) if (v!=p&&v!=hv[u]) hld(v, u, v);
}
void update(int u, int x, int y)
{
while (1)
{
//cout<<"debug "<<u<<' '<<hd[u]<<'\n';
auto prev=s.getrange(hd[u]);
//cout<<"euler "<<in[hd[u]]<<' '<<out[hd[u]]<<'\n';
//cout<<"prev "<<prev.first<<' '<<prev.second<<'\n';
s.update(1, n, 1, in[u], x, y);
auto cur=s.getrange(hd[u]);
//cout<<"after "<<cur.first<<' '<<cur.second<<'\n';
x=cur.first-prev.first, y=cur.second-prev.second;
if (pa[hd[u]]==-1) break;
u=pa[hd[u]];
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n=N;
for (int i=0; i<n-1; i++) d[A[i]].push_back(B[i]), d[B[i]].push_back(A[i]);
dfssz(1, -1);
//for (int i=1; i<=n; i++) cout<<"here "<<i<<' '<<hv[i]<<' '<<pa[i]<<'\n';
hld(1, 1, 1);
//for (int i=1; i<=n; i++) cout<<"hd "<<i<<' '<<hd[i]<<'\n';
}
int cat(int v) {
type[v]=1;
update(v, 0, inf);
auto res=s.getrange(1);
return min(res.first, res.second);
}
int dog(int v) {
type[v]=2;
update(v, inf, 0);
auto res=s.getrange(1);
return min(res.first, res.second);
}
int neighbor(int v) {
if (type[v]==1) update(v, 0, -inf);
else update(v, -inf, 0);
auto res=s.getrange(1);
return min(res.first, res.second);
}
