题解：P9597 [JOI Open 2018] 猫或狗 / Cats or Dogs

/*

		2025.11.4

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005,inf=0x3f3f3f3f,mod=998244353;
struct matrix{
	int n,m,a[2][2];
	void init(){n=m=2,a[0][0]=a[1][1]=0,a[0][1]=a[1][0]=inf;}
	const matrix operator *(const matrix y)const{
		matrix ans;ans.n=n,ans.m=y.m;memset(ans.a,0x3f,sizeof(ans.a));
		for(int i=0;i<n;i++)for(int j=0;j<y.m;j++)for(int k=0;k<m;k++)ans.a[i][j]=min(ans.a[i][j],a[i][k]+y.a[k][j]);
		return ans;
	}
}f[MAXN],tmp,gg[MAXN],t[3];
struct node{int l,r;matrix w,mask,ww;}tree[MAXN*4];
int n,a[MAXN];
int dfn[MAXN],rev[MAXN],top[MAXN],ed[MAXN],cnt;
int son[MAXN],si[MAXN],dep[MAXN],mx[MAXN],fa[MAXN];
vector<int>g[MAXN];
void pre_dfs(int x){
	si[x]=1;
	for(int i:g[x]){
		if(si[i])continue;
		pre_dfs(i);si[x]+=si[i];fa[i]=x;
		if(si[i]>si[son[x]])son[x]=i;
	}
}
void dfs(int x,int top){
	dfn[x]=++cnt;rev[cnt]=x;::top[x]=top;
	if(son[x])dfs(son[x],top);
	for(int i:g[x])if(!dfn[i]&&i!=son[x])dfs(i,i);
}
void build(int x,int l,int r){
	tree[x].l=l,tree[x].r=r;
	if(l==r){
		tree[x].w.n=tree[x].w.m=2;
		tree[x].w.a[0][1]=tree[x].w.a[1][0]=1;tree[x].w.a[0][0]=tree[x].w.a[1][1]=0;
		tree[x].mask=tree[x].w,tree[x].ww=tree[x].w*tree[x].mask;
		return ;
	}
	int mid=(l+r)>>1;
	build(x*2,l,mid);build(x*2+1,mid+1,r);
	tree[x].ww=tree[x*2+1].ww*tree[x*2].ww;
}
matrix ask(int x,int l,int r,int op){
	if(l>r){matrix ans;ans.init();return ans;}
	if(tree[x].l>=l&&tree[x].r<=r)return (op?tree[x].w:tree[x].ww);
	int mid=(tree[x].l+tree[x].r)>>1;
	matrix ans;ans.init();
	if(l<=mid)ans=ask(x*2,l,r,op);
	if(r>mid)ans=ask(x*2+1,l,r,op)*ans;
	return ans;
}
void add(int x,int l,const matrix &t,const matrix &t2){
	if(tree[x].l==tree[x].r){
		tree[x].w=t,tree[x].mask=t2,tree[x].ww=tree[x].w*tree[x].mask;
		return ;
	}
	int mid=(tree[x].l+tree[x].r)>>1;
	if(l<=mid)add(x*2,l,t,t2);
	else add(x*2+1,l,t,t2);
	tree[x].ww=tree[x*2+1].ww*tree[x*2].ww;
}
int st(int x,int t){
	matrix now=ask(1,dfn[x],dfn[x],1);
	add(1,dfn[x],now,::t[t]);a[x]=t;
	int tp=top[x];
	while(tp!=1){
		matrix tf=tmp*ask(1,dfn[tp],ed[tp],0);
		now=ask(1,dfn[fa[tp]],dfn[fa[tp]],1);
		int f0=now.a[0][0],f1=now.a[1][1];
		f0-=min(f[tp].a[0][0],f[tp].a[0][1]+1),f1-=min(f[tp].a[0][1],f[tp].a[0][0]+1);
		f0+=min(tf.a[0][0],tf.a[0][1]+1),f1+=min(tf.a[0][1],tf.a[0][0]+1);
		f[tp]=tf;
		now.a[0][0]=f0,now.a[1][0]=f0+1,now.a[0][1]=f1+1,now.a[1][1]=f1;
		add(1,dfn[fa[tp]],now,::t[a[fa[tp]]]);
		x=fa[tp],tp=top[x];
	}
	now=tmp*ask(1,1,ed[1],0);int ttt=min(now.a[0][0],now.a[0][1]);
	return ttt;
}
int cat(int v){return st(v,0);}
int dog(int v){return st(v,1);}
int neighbor(int v){return st(v,2);}
void initialize(int N,vector<int>A,vector<int>B){
	n=N;
	t[2].n=t[2].m=2;t[2].a[0][0]=t[2].a[1][1]=0,t[2].a[1][0]=t[2].a[0][1]=inf;
	t[0]=t[2],t[1]=t[2];
	t[0].a[0][0]=inf,t[0].a[1][0]=inf,t[1].a[1][1]=inf;t[1].a[1][0]=inf;
	tmp.n=1,tmp.m=2;tmp.a[0][0]=tmp.a[0][1]=0;
	for(int i=0;i<n-1;i++)g[A[i]].push_back(B[i]),g[B[i]].push_back(A[i]);
	for(int i=1;i<=n;i++)a[i]=2,f[i].n=1,f[i].m=2,f[i].a[0][0]=f[i].a[0][1]=0;
	pre_dfs(1);dfs(1,1);
	for(int i=1;i<=n;i++)mx[top[i]]=max(mx[top[i]],dfn[i]);
	for(int i=1;i<=n;i++)ed[i]=mx[top[i]];
	build(1,1,n);
}