#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;
struct Node{
ll cc;
ll dd;
ll cd;
ll dc;
Node(ll cc=1000000000000000, ll dd=1000000000000000, ll cd=1000000000000000 , ll dc=1000000000000000):cc(cc),dd(dd),cd(cd),dc(dc){}
};
Node comb(Node a, Node b){
Node res;
res.cc=min(min( a.cc+b.cc , a.cd+b.dc),min( a.cc+b.dc+1 , a.cd+b.cc+1)); //1
res.dd=min(min( a.dd+b.dd , a.dc+b.cd),min( a.dd+b.cd+1 , a.dc+b.dd+1)); //2
res.cd=min(min( a.cc+b.cd , a.cd+b.dd),min( a.cc+b.dd+1 , a.cd+b.cd+1)); //3
res.dc=min(min( a.dd+b.dc , a.dc+b.cc),min( a.dd+b.cc+1 , a.dc+b.dc+1)); //4
res.cc=min(res.cc,(ll)1000000000000000);
res.dd=min(res.dd,(ll)1000000000000000);
res.cd=min(res.cd,(ll)1000000000000000);
res.dc=min(res.dc,(ll)1000000000000000);
return res;
}
struct STree{
ll n;
vector<Node> st;
STree(ll n=0):n(n), st(4*n+5,Node()) {}
void upd(ll k, ll l, ll r, ll p, ll t, ll v){
if(l+1==r){
if(t==1) st[k].cc=v;
if(t==2) st[k].dd=v;
if(t==3) st[k].cd=v;
if(t==4) st[k].dc=v;
return;}
ll mid=(l+r)/2;
if(mid>p) upd(2*k,l,mid,p,t,v);
else upd(2*k+1,mid,r,p,t,v);
st[k]=comb(st[2*k],st[2*k+1]);
}
void upd(ll k, ll l, ll r, ll p, Node v){
if(l+1==r) { st[k]=v; return; }
ll mid=(l+r)/2;
if(mid>p) upd(2*k,l,mid,p,v);
else upd(2*k+1,mid,r,p,v);
st[k]=comb(st[2*k],st[2*k+1]);
}
Node queryp(ll k, ll l, ll r, ll p){
if(l+1==r) return st[k];
ll mid=(l+r)/2;
if(mid>p) return queryp(2*k,l,mid,p);
else return queryp(2*k+1,mid,r,p);
}
Node query(){
return st[1];
}
void upd(ll p,ll t, ll v){ upd(1,0,n,p,t,v); }
void upd(ll p, Node v){ upd(1,0,n,p,v); }
Node queryp(ll p){ return queryp(1,0,n,p); }
};
ll dp[MAXN][5];
ll best[MAXN];
vector<ll> adj[MAXN];
ll color[MAXN];
ll par[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;
}
ll dep[MAXN];
void dfs(ll nd, ll p , ll lvl){
dep[nd]=0;
best[nd]=-1;
par[nd]=p;
for(auto i:adj[nd]) if(i!=p){
dfs(i,nd,lvl+1);
if(dep[i]+1>dep[nd]) best[nd]=i , dep[nd]=dep[i]+1;
}
}
vector<STree> st;
vector<ll> repchain;
vector<ll> szchain;
ll mychain[MAXN];
ll myposchain[MAXN];
ll rep = 0;
ll last = 0;
ll sz = 0;
void heavy_chain( ll nd , ll p){
if(p!=-1 && best[p]!=nd){
rep=nd;
sz=0;
}
mychain[nd]=last;
myposchain[nd]=sz;
sz++;
if(best[nd]==-1){
st.pb(STree(sz));
repchain.pb(rep);
szchain.pb(sz);
last++;
return;
}
heavy_chain(best[nd],nd);
for(auto i:adj[nd]) if(i!=p && i!=best[nd]){
heavy_chain(i,nd);
}
}
void calc(ll nd){
if(par[nd]==-1) return;
ll nextchain = mychain[par[nd]];
ll next = repchain[nextchain];
ll actchain = mychain[nd];
//cout<<"haciendo queryp "<<nextchain<<" "<<myposchain[par[nd]]<<'\n';
Node connectnd = st[nextchain].queryp(myposchain[par[nd]]);
//cout<<"haciendo query\n";
Node chainval = st[actchain].query();
Node bestnd = connectnd;
bestnd.cc+=min(min(chainval.cc,chainval.cd),min(chainval.dd+1,chainval.dc+1));
bestnd.dd+=min(min(chainval.cc+1,chainval.cd+1),min(chainval.dd,chainval.dc));
bestnd.cd+=min(min(chainval.cc+1,chainval.cd+1),min(chainval.dd,chainval.dc));
bestnd.dc+=min(min(chainval.cc,chainval.cd),min(chainval.dd+1,chainval.dc+1));
st[nextchain].upd(myposchain[par[nd]],bestnd);
calc(next);
}
void rest(ll nd){
if(par[nd]==-1) return;
ll nextchain = mychain[par[nd]];
ll next = repchain[nextchain];
ll actchain = mychain[nd];
rest(next);
Node connectnd = st[nextchain].queryp(myposchain[par[nd]]);
Node chainval = st[actchain].query();
Node bestnd = connectnd;
bestnd.cc-=min(min(chainval.cc,chainval.cd),min(chainval.dd+1,chainval.dc+1));
bestnd.dd-=min(min(chainval.cc+1,chainval.cd+1),min(chainval.dd,chainval.dc));
bestnd.cd-=min(min(chainval.cc+1,chainval.cd+1),min(chainval.dd,chainval.dc));
bestnd.dc-=min(min(chainval.cc,chainval.cd),min(chainval.dd+1,chainval.dc+1));
st[nextchain].upd(myposchain[par[nd]],bestnd);
}
ll minres(){
//cout<<"--------------------------------\n";
Node nd = st[0].query();
/*forn(i,0,SZ(st)){
//cout<<"chain "<<i<<": ";
forn(j,0,szchain[i])
cout<<" ("<<st[i].queryp(j).cc<<" , "<<st[i].queryp(j).dd<<" , "<<st[i].queryp(j).cd<<" , "<<st[i].queryp(j).dc<<") "<<'\n';
} cout.flush();*/
return min(min(nd.cc,nd.dd),min(nd.cd,nd.dc));
}
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);
//cout<<"Precalculo\n";
dfs(0,-1,0);
//cout<<"Profundidades listas\n";
heavy_chain(0,-1);
//cout<<"Cadenas pesadas calculadas\n";
forn(i,0,n){
//cout<<" seteando en "<<mychain[i]<<" "<<myposchain[i]<<" cats en 0\n";
st[mychain[i]].upd(myposchain[i],1,0);
//cout<<" seteando en "<<mychain[i]<<" "<<myposchain[i]<<" dogs en 0\n";
st[mychain[i]].upd(myposchain[i],2,0);
}
//cout<<"Segment tree actualizado\n";
forn(i,1,n){
if(SZ(adj[i])==1) calc(repchain[mychain[i]]);
}
//cout<<"Todo seteado \n";
//cout<<minres()<<'\n';
}
int cat(int v) { v--;
color[v]=1;
//cout<<"Mychain "<<mychain[v]<<" Myposchain "<<myposchain[v]<<'\n';
rest(repchain[mychain[v]]);
st[mychain[v]].upd(myposchain[v],2,st[mychain[v]].queryp(myposchain[v]).dd+100000000);
calc(repchain[mychain[v]]);
return minres();
}
int dog(int v) { v--;
color[v]=2;
//cout<<"Mychain "<<mychain[v]<<" Myposchain "<<myposchain[v]<<'\n';
rest(repchain[mychain[v]]);
st[mychain[v]].upd(myposchain[v],1,st[mychain[v]].queryp(myposchain[v]).cc+100000000);
calc(repchain[mychain[v]]);
return minres();
}
int neighbor(int v) { v--;
//cout<<"Mychain "<<mychain[v]<<" Myposchain "<<myposchain[v]<<'\n';
rest(repchain[mychain[v]]);
if(color[v]==1){
st[mychain[v]].upd(myposchain[v],2,st[mychain[v]].queryp(myposchain[v]).dd-100000000);
}else{
st[mychain[v]].upd(myposchain[v],1,st[mychain[v]].queryp(myposchain[v]).cc-100000000);
}
color[v]=0;
calc(repchain[mychain[v]]);
return minres();
}
