#include "catdog.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n;
int timer;
int a[MAXN];
int dp[MAXN][2];
int bl[MAXN][2];
int parent[MAXN];
std::vector <int> g[MAXN];
void buildDFS(int node, int par)
{
parent[node] = par;
for (int &u : g[node])
{
if (u == par)
{
std::swap(u, g[node].back());
g[node].pop_back();
break;
}
}
for (const int &u : g[node])
{
buildDFS(u, node);
}
}
int f(int node, int type)
{
if (bl[node][type] == timer)
{
return dp[node][type];
}
bl[node][type] = timer;
dp[node][type] = INF;
if (a[node] != (type ^ 1))
{
int curr = 0;
for (const int &u : g[node])
{
curr += std::min(f(u, type ^ 1) + 1, f(u, type));
}
dp[node][type] = std::min(dp[node][type], curr);
} else
{
int curr = 1;
for (const int &u : g[node])
{
curr += std::min(f(u, type ^ 1), f(u, type) + 1);
}
dp[node][type] = std::min(dp[node][type], curr);
}
return dp[node][type];
}
void initialize(int N, std::vector <int> A, std::vector <int> B)
{
n = N;
std::fill(a + 1, a + 1 + n, 2);
for (int i = 0 ; i < n - 1 ; ++i)
{
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
buildDFS(1, 0);
}
int cat(int v)
{
timer++;
a[v] = 0;
return std::min(f(1, 0), f(1, 1));
}
int dog(int v)
{
timer++;
a[v] = 1;
return std::min(f(1, 0), f(1, 1));
}
int neighbor(int v)
{
timer++;
a[v] = 2;
return std::min(f(1, 0), f(1, 1));
}
/*
9
5 3
4 9
5 4
4 1
5 7
7 6
4 8
2 3
6
2 9
2 5
1 1
2 2
1 4
1 3
*/
