#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; struct Info { int dp[3]; void init() { dp[0] = dp[1] = dp[2] = +INF; } void makeType(int x) { init(); dp[x] = 0; } Info operator + (const Info &other) const { Info ret; ret.init(); for (int x = 0; x < 3; x++) { for (int y = 0; y < 3; y++) { ret.dp[x] = std::min(ret.dp[x], dp[x] + other.dp[y] + 1); if ((x | y) != 3) { ret.dp[x | y] = std::min(ret.dp[x | y], dp[x] + other.dp[y]); } } } return ret; }; }; Info dp[MAXN]; 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].makeType(type[u]); for (int v : g[u]) { dfsDP(v); dp[u] = dp[u] + dp[v]; } } 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].dp[0], dp[0].dp[1], dp[0].dp[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(); }