#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[100005];
int state[100005];
int subtreeCats[100005];
int subtreeDogs[100005];
int totalCats, totalDogs;
int danger;
void dfs(int node, int parent) {
subtreeCats[node] = (state[node] == 1) ? 1 : 0;
subtreeDogs[node] = (state[node] == 2) ? 1 : 0;
for (int next : adj[node]) {
if (next != parent) {
dfs(next, node);
subtreeCats[node] += subtreeCats[next];
subtreeDogs[node] += subtreeDogs[next];
}
}
if (parent != -1) {
int catsAbove = totalCats - subtreeCats[node];
int dogsAbove = totalDogs - subtreeDogs[node];
if ((subtreeCats[node] > 0 && dogsAbove > 0) ||
(subtreeDogs[node] > 0 && catsAbove > 0)) {
danger++;
}
}
}
int calculateDanger() {
totalCats = 0;
totalDogs = 0;
for (int i = 1; i <= n; i++) {
if (state[i] == 1) totalCats++;
if (state[i] == 2) totalDogs++;
}
if (totalCats == 0 || totalDogs == 0) return 0;
danger = 0;
dfs(1, -1);
return danger;
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for (int i = 0; i < N - 1; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
fill(state + 1, state + N + 1, 0);
}
int cat(int v) { state[v] = 1; return calculateDanger(); }
int dog(int v) { state[v] = 2; return calculateDanger(); }
int neighbor(int v) { state[v] = 0; return calculateDanger(); }
