#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 = 100000+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(); }