#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[100005];
int state[100005];
pair<bool,bool> dfs(int node, int parent) {
bool hasCat = (state[node] == 1);
bool hasDog = (state[node] == 2);
for (int next : adj[node]) {
if (next != parent) {
auto [c, d] = dfs(next, node);
hasCat |= c;
hasDog |= d;
}
}
return {hasCat, hasDog};
}
int danger;
void dfs2(int node, int parent) {
bool nodeCat = (state[node] == 1);
bool nodeDog = (state[node] == 2);
for (int next : adj[node]) {
if (next != parent) {
auto [childCat, childDog] = dfs(next, node);
auto [totalCat, totalDog] = dfs(1, -1);
bool restCat = totalCat && !(!totalCat);
bool restDog = totalDog;
dfs2(next, node);
}
}
}
int calculateDanger() {
danger = 0;
auto [totalCat, totalDog] = dfs(1, -1);
if (!totalCat || !totalDog) return 0;
function<void(int, int)> solve = [&](int node, int par) {
for (int next : adj[node]) {
if (next != par) {
auto [childCat, childDog] = dfs(next, node);
bool parentCat = totalCat;
bool parentDog = totalDog;
if (childCat && !childDog && parentDog) danger++;
else if (childDog && !childCat && parentCat) danger++;
else if (childCat && childDog) danger++;
solve(next, node);
}
}
};
solve(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(); }
