#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector <ll> adj[1005];
ll cnt[1005][2][2], p[1005], state[1005];
/*
0->current, 1->dibawah
*/
int x;
void dfs(ll idx, ll par) {
for (auto i : adj[idx]) {
if (i != par) {
p[i] = idx;
dfs(i, idx);
}
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
for (int i = 0; i < N; i++) state[i] = -1;
for (int i = 0; i < N - 1; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1, -1);
}
ll ans = 0;
/*
0 -> cat
1 -> dog
*/
int cat(int v) {
cnt[v][0][1] = cnt[v][0][0];
cnt[v][1][1] = cnt[v][1][0];
ll c = 0, d = 0;
c = cnt[v][0][0] - 1, d = cnt[v][1][0];
cnt[v][0][0] = 1, cnt[v][1][0] = 0;
ans += cnt[v][1][1];
state[v] = 0;
v = p[v];
while (v) {
if (state[v] != -1) {
cnt[v][0][1] -= c, cnt[v][1][1] -= d;
ans -= (state[v] == 0 ? d : c);
break;
}
cnt[v][0][0] -= c, cnt[v][1][0] -= d;
v = p[v];
}
return ans;
}
int dog(int v) {
cnt[v][0][1] = cnt[v][0][0];
cnt[v][1][1] = cnt[v][1][0];
ll c = 0, d = 0;
c = cnt[v][0][0], d = cnt[v][1][0] - 1;
cnt[v][0][0] = 0, cnt[v][1][0] = 1;
ans += cnt[v][0][1];
state[v] = 1;
v = p[v];
while (v) {
if (state[v] != -1) {
cnt[v][0][1] -= c, cnt[v][1][1] -= d;
ans -= (state[v] == 0 ? d : c);
break;
}
cnt[v][0][0] -= c, cnt[v][1][0] -= d;
v = p[v];
}
return ans;
}
int neighbor(int v) {
ll c = 0, d = 0;
c = cnt[v][0][0] - cnt[v][0][1], d = cnt[v][1][0] - cnt[v][1][1];
ans -= cnt[v][state[v] ^ 1][1];
cnt[v][0][0] = cnt[v][0][1];
cnt[v][1][0] = cnt[v][1][1];
cnt[v][0][1] = cnt[v][1][1] = 0;
state[v] = -1;
v = p[v];
while (v) {
if (state[v] != -1) {
cnt[v][0][1] -= c, cnt[v][1][1] -= d;
ans -= (state[v] == 0 ? d : c);
break;
}
cnt[v][0][0] -= c, cnt[v][1][0] -= d;
v = p[v];
}
return ans;
}
