#include "catdog.h" #include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; const int nx=1e5+5; struct dak { int dp[2][2]; dak() { memset(dp, 0, sizeof(dp)); } } nod[nx<<2]; dak operator +(dak a, dak b) { dak c; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) c.dp[i][j]=inf; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int l = 0; l < 2; l++) for(int r = 0; r < 2; r++) c.dp[i][r]=min(c.dp[i][r], a.dp[i][j]+b.dp[l][r]+(j!=l)); return c; } vector<int> adj[nx]; int n; int par[nx], sz[nx], ani[nx], leaf[nx], last[nx]; int top[nx], chain=1, id[nx], pos[nx], tim=0; void dfs(int u) { sz[u]=1; for(int v:adj[u]) { if(v==par[u]) continue; par[v]=u; dfs(v); sz[u]+=sz[v]; } } void hld(int u) { if(!top[chain]) top[chain]=u; last[chain]=u; id[u]=chain; pos[u]=++tim; int sp=-1; for(int v:adj[u]) if(v!=par[u]) if(sp==-1 || sz[sp]<sz[v]) sp=v; if(sp!=-1) hld(sp); for(int v:adj[u]) if(v!=par[u] && v!=sp) chain++, hld(v); } void build(int id, int l, int r) { if(l==r) return void(leaf[l]=id); int mid=(l+r)>>1; build(id<<1, l, mid); build(id<<1|1, mid+1, r); } void update(int p, int cat, int dog) { int id=leaf[p]; nod[id].dp[0][0]+=cat; nod[id].dp[1][1]+=dog; while(id>1) { id>>=1; nod[id]=nod[id<<1]+nod[id<<1|1]; } } dak get(int id, int l, int r, int u, int v) { if(l>=u && r<=v) return nod[id]; int mid=(l+r)>>1; if(v<=mid) return get(id<<1, l, mid, u, v); if(u>mid) return get(id<<1|1, mid+1, r, u, v); return get(id<<1, l, mid, u, v)+get(id<<1|1, mid+1, r, u, v); } void initialize(int N, vector<int> a, vector<int> b) { n=N; for(int i = 0; i < n-1; i++) { adj[a[i]].emplace_back(b[i]); adj[b[i]].emplace_back(a[i]); } for(int i = 1; i <= n; i++) ani[i]=0; dfs(1); hld(1); build(1, 1, n); } dak sus(dak a) { dak b; b.dp[0][0]=min({a.dp[0][0], a.dp[0][1], a.dp[1][0]+1, a.dp[1][1]+1}); b.dp[1][1]=min({a.dp[1][1], a.dp[1][0], a.dp[0][1]+1, a.dp[0][0]+1}); return b; } dak answer(int u) { int t=top[id[u]]; return get(1, 1, n, pos[t], pos[last[id[u]]]); } void solve(int u, int cat, int dog) { while(u>0) { dak cur=sus(answer(u)); update(pos[u], cat, dog); dak nw=sus(answer(u)); cat=nw.dp[0][0]-cur.dp[0][0]; dog=nw.dp[1][1]-cur.dp[1][1]; u=par[top[id[u]]]; } } int ha(dak a) { return min({a.dp[0][0], a.dp[0][1], a.dp[1][0], a.dp[1][1]}); } int cat(int u) { ani[u]=1; solve(u, 0, inf); return ha(answer(1)); } int dog(int u) { ani[u]=2; solve(u, inf, 0); return ha(answer(1)); } int neighbor(int u) { if(ani[u]==1) solve(u, 0, -inf); else solve(u, -inf, 0); ani[u]=0; return ha(answer(1)); }