#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; vector<ll> adj[MAXN*3]; ll color[MAXN*3]; pair<ll,ll> ract[MAXN*3]; ll n; ll last; ll res = 0; pair<ll,ll> act = {0,0}; void dfs(ll nd, ll p){ for(auto i:adj[nd]) if(i!=p){ if(color[i]==1){ act.fst++; continue; } if(color[i]==2){ act.snd++; continue; } dfs(i,nd); } } void ndfs(ll nd, ll p){ ract[nd]=act; for(auto i:adj[nd]) if(i!=p && color[i]==0){ ndfs(i,nd); } } void initialize(int N, std::vector<int> A, std::vector<int> B) { n = N; last=n; forn(i,0,n-1){ A[i]--; B[i]--; adj[A[i]].pb(last); adj[last].pb(A[i]); adj[B[i]].pb(last); adj[last].pb(B[i]); last++; } mset(color,0); forn(i,0,MAXN*3) ract[i]={0,0}; } int cat(int v) { v--; color[v]=1; res-=min(ract[v].fst,ract[v].snd); for(auto i:adj[v]){ act={0,0}; dfs(i,-1); res+=min(act.fst,act.snd); ndfs(i,-1); } return res; } int dog(int v) { v--; color[v]=2; res-=min(ract[v].fst,ract[v].snd); for(auto i:adj[v]){ act={0,0}; dfs(i,-1); res+=min(act.fst,act.snd); ndfs(i,-1); } return res; } int neighbor(int v) { v--; color[v]=0; for(auto i:adj[v]){ res-=min(ract[i].fst,ract[i].snd); } act={0,0}; dfs(v,-1); res+=min(act.fst,act.snd); ndfs(v,-1); return res; }