#include "catdog.h" #include <bits/stdc++.h> #define fst first #define snd second #define pb push_back #define SZ(x) (int)x.size() #define ALL(x) x.begin(),x.end() #define forn(i,a,b) for(int i = a; i<b;i++) #define mset(a,v) memset(a,v,sizeof(a)) #define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; const int MAXN = 2000+5; ll dp[MAXN][5]; vector<ll> adj[MAXN]; ll color[MAXN]; ll n; ll f(ll x, ll y, ll p){ ll &res = dp[x][y]; if(res!=-1) return res; if(color[x]!=0 && color[x]!=y) return 1000000000; res=0; for(auto i:adj[x]) if(i!=p){ res+=min(f(i,1+(y%2),x)+1,f(i,y,x)); } //cout<<x<<" "<<y<<" "<<color[x]<<" "<<p<<" ----------> "<<res<<'\n'; return res; } void initialize(int N, std::vector<int> A, std::vector<int> B) { n = N; forn(i,0,n-1){ A[i]--; B[i]--; adj[A[i]].pb(B[i]); adj[B[i]].pb(A[i]); } mset(color,0); } int cat(int v) { v--; color[v]=1; mset(dp,-1); return min(f(0,1,-1),f(0,2,-1)); } int dog(int v) { v--; color[v]=2; mset(dp,-1); return min(f(0,1,-1),f(0,2,-1)); } int neighbor(int v) { v--; color[v]=0; mset(dp,-1); return min(f(0,1,-1),f(0,2,-1)); }