#include "catdog.h" #include<bits/stdc++.h> using namespace std; #define foru(i,a,b) for(int i=(a); i<=(b); ++i) #define ford(i,a,b) for(int i=(a); i>=(b); --i) #define rep(i,a) for(int i=0; i<(a); ++i) #define sz(a) (int)(a).size() #define all(a) (a).begin(),(a).end() #define bit(s,i) (((s)>>(i))&1) #define ii pair<int,int> #define vi vector<int> #define vii vector<ii> #define fi first #define se second #define ll long long #define eb emplace_back #define pb push_back #define __builtin_popcount __builtin_popcountll #define _ << " " << template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;} template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;} const int INF=1e9; const int N=1e5+5; int n,sz[N]; vi adj[N]; void pre(int u, int p=-1){ sz[u]=1; for(int v:adj[u]) if(v!=p){ pre(v,u); sz[u]+=sz[v]; } } int idCh[N],head[N],lst[N],bigC[N],tin[N],tout[N],par[N],tim,curCh=1; void hld(int u, int p=-1){ par[u]=p; if(!head[curCh]){ head[curCh]=u; } lst[curCh]=u; idCh[u]=curCh; tin[u]=++tim; bigC[u]=-1; for(int v:adj[u]) if(v!=p) if(bigC[u]==-1 || sz[v]>sz[bigC[u]]) bigC[u]=v; if(bigC[u]!=-1) hld(bigC[u],u); for(int v:adj[u]) if(v!=p && v!=bigC[u]){ ++curCh; hld(v,u); } tout[u]=tim; } struct Node{ int dp[2][2]; Node(){ memset(dp,0,sizeof(dp)); } } st[N<<2]; Node comb(Node a, Node b){ Node c; c.dp[0][0]=c.dp[1][1]=c.dp[0][1]=c.dp[1][0]=INF; rep(ia,2) rep(ja,2){ rep(ib,2) rep(jb,2){ mini(c.dp[ia][jb], a.dp[ia][ja]+b.dp[ib][jb]+(ja!=ib)); } } return c; } void upd(int x, int cat, int dog){ int id=1, l=1, r=n; while(l<r){ int m=(l+r)>>1; if(x<=m) id=id<<1, r=m; else id=id<<1|1, l=m+1; } st[id].dp[0][0]+=cat; st[id].dp[1][1]+=dog; while(id>1){ id/=2; st[id]=comb(st[id<<1],st[id<<1|1]); } } void init(int id=1, int l=1, int r=n){ if(l==r){ st[id].dp[0][0]=st[id].dp[1][1]=0; st[id].dp[0][1]=st[id].dp[1][0]=INF; return; } int m=(l+r)>>1; init(id<<1,l,m); init(id<<1|1,m+1,r); st[id]=comb(st[id<<1],st[id<<1|1]); } Node get(int u, int v, int id=1, int l=1, int r=n){ if(u<=l&&r<=v)return st[id]; int m=(l+r)>>1; if(v<=m) return get(u,v,id<<1,l,m); if(u>m) return get(u,v,id<<1|1,m+1,r); return comb(get(u,v,id<<1,l,m),get(u,v,id<<1|1,m+1,r)); } void initialize(int nn, vi aa, vi bb) { n=nn; rep(i,n-1){ adj[aa[i]].eb(bb[i]); adj[bb[i]].eb(aa[i]); } pre(1); hld(1); init(); } Node trans(Node x){ Node y; y.dp[0][0]=min({x.dp[0][0],x.dp[0][1],x.dp[1][0]+1,x.dp[1][1]+1}); y.dp[1][1]=min({x.dp[1][0],x.dp[1][1],x.dp[0][0]+1,x.dp[0][1]+1}); return y; } void updcd(int x, int cat, int dog){ while(x>=1){ int t=head[idCh[x]]; Node cur=trans(get(tin[t],tin[lst[idCh[t]]])); upd(tin[x],cat,dog); Node nw=trans(get(tin[t],tin[lst[idCh[t]]])); cat=nw.dp[0][0]-cur.dp[0][0]; dog=nw.dp[1][1]-cur.dp[1][1]; x=par[t]; } } int ani[N]; int cat(int v) { ani[v]=1; updcd(v,0,INF); Node t=get(tin[1],tin[lst[idCh[1]]]); int res=min({t.dp[0][0],t.dp[0][1],t.dp[1][1],t.dp[1][0]}); return res; } int dog(int v) { ani[v]=2; updcd(v,INF,0); Node t=get(tin[1],tin[lst[idCh[1]]]); int res=min({t.dp[0][0],t.dp[0][1],t.dp[1][1],t.dp[1][0]}); return res; } int neighbor(int v) { if(ani[v]==1){ updcd(v,0,-INF); } else{ updcd(v,-INF,0); } ani[v]=0; Node t=get(tin[1],tin[lst[idCh[1]]]); int res=min({t.dp[0][0],t.dp[0][1],t.dp[1][1],t.dp[1][0]}); return res; }