#include "catdog.h" #include <iostream> #include <vector> #include <algorithm> #include <cassert> using ll = long long; #define debug(x) #x << " = " << x < '\n' const int INF = 1e9; const int MAXN = 1e5; int dp[MAXN][3]; int type[MAXN]; std::vector<int> g[MAXN]; void dfs(int u, int p) { if (p != u) { g[u].erase(std::find(g[u].begin(), g[u].end(), p)); } for (int v : g[u]) { dfs(v, u); } } void dfsDP(int u) { dp[u][0] = dp[u][1] = dp[u][2] = +INF; dp[u][type[u]] = 0; for (int v : g[u]) { dfsDP(v); int nw[3] = {+INF, +INF, +INF}; for (int x = 0; x < 3; x++) { for (int y = 0; y < 3; y++) { nw[x] = std::min(nw[x], dp[u][x] + dp[v][y] + 1); if ((x | y) != 3) { nw[x | y] = std::min(nw[x | y], dp[u][x] + dp[v][y]); } } } dp[u][0] = nw[0]; dp[u][1] = nw[1]; dp[u][2] = nw[2]; } } void initialize(int N, std::vector<int> A, std::vector<int> B) { for (int i = 0; i + 1 < N; i++) { A[i]--, B[i]--; g[A[i]].push_back(B[i]); g[B[i]].push_back(A[i]); } dfs(0, 0); } int getAnswer() { dfsDP(0); return std::min({dp[0][0], dp[0][1], dp[0][2]}); } int cat(int v) { v--; type[v] = 1; return getAnswer(); } int dog(int v) { v--; type[v] = 2; return getAnswer(); } int neighbor(int v) { v--; type[v] = 0; return getAnswer(); }