[ARC097F]Monochrome Cat

题意：一棵树，每个节点是黑色或白色，你可以从任意节点开始进行一些操作并在任意节点结束，如果当前在$x$，那么一次操作可以是：1.走到相邻节点$y$并翻转$y$的颜色，2.翻转$x$的颜色，问把所有节点都变黑最少要多少次操作

首先当然要把黑色叶子全部删掉，这个类似拓扑排序一样做即可

然后证一个小结论：不会有一条边被经过$\gt2$次

设$(x,y)$被经过$3$次，那么操作序列为$A\Rightarrow(x\rightarrow y)\Rightarrow B\Rightarrow(y\rightarrow x)\Rightarrow C\Rightarrow(x\rightarrow y)\Rightarrow D$，我们可以把操作序列变为$A\Rightarrow C\Rightarrow\text~x\Rightarrow(x\rightarrow y)\Rightarrow\text~y\Rightarrow B\Rightarrow D$，这样等价并且没有增加操作次数

所以最优解形如：选定起点$s$和终点$t$，$s\rightarrow t$路径上的边只经过一次，其他边经过两次，并在过程中适时使用操作$2$

更进一步：存在最优解使得$s,t$都是叶子

假设起点为$x$，终点为$y$且$y$不是叶子，$z$是$y$往远离$x$方向的第一个节点，那么把原来的$(y\rightarrow z)\Rightarrow X\Rightarrow(z\rightarrow y)$变成$\text~y\Rightarrow(y\rightarrow z)\Rightarrow X$即可，同样不增加操作次数

现在考虑怎么求答案，如果$s=t$，设$d_x$为$x$的度数并记$v_x=\left[(d_x\equiv1(\bmod2),c_x=B)\text{ or }(d_x\equiv0(\bmod2),c_x=W)\right]$，那么答案是$2|E|+\sum\limits_xv_x$

当$t$移动时，$s\rightarrow t$上的边经过次数$-1$，$s\rightarrow t$这条链上$\neq t$的点（以下记这条链为$[s,t)$）的贡献也要重新计算，要加上$-\text{dis}(s,t)+\sum\limits_{x\in[s,t)}-[v_x=1]+[v_x=0]$

所以如果我们给每个点$x$一个权值$-[v_x=1]+[v_x=0]-1$，找到最小的叶子到叶子的链即可，dfs一遍统计答案即可

monochrome：单色的，黑白的

#include<stdio.h>
#include<algorithm>
using namespace std;
int h[100010],nex[200010],to[200010],M,n;
void add(int a,int b){
	M++;
	to[M]=b;
	nex[M]=h[a];
	h[a]=M;
}
int d[100010],q[100010];
bool del[100010];
char s[100010];
void topsort(){
	int head,tail,x,i;
	head=1;
	tail=0;
	for(i=1;i<=n;i++){
		if(s[i]=='B'&&d[i]==1)q[++tail]=i;
	}
	while(head<=tail){
		x=q[head++];
		del[x]=1;
		for(i=h[x];i;i=nex[i]){
			if(d[to[i]])d[to[i]]--;
			if(s[to[i]]=='B'&&d[to[i]]==1&&!del[to[i]])q[++tail]=to[i];
		}
	}
}
int f[100010],sum,mn;
int tp(int x){return(d[x]&1)^(s[x]=='W');}
int val(int x){return tp(x)==1?-2:0;}
void dfs(int fa,int x){
	sum+=(tp(x)==1)+2;
	f[x]=val(x);
	for(int i=h[x];i;i=nex[i]){
		if(to[i]!=fa&&!del[to[i]]){
			dfs(x,to[i]);
			mn=min(mn,f[x]+f[to[i]]);
			f[x]=min(f[x],f[to[i]]+val(x));
		}
	}
}
int main(){
	int i,x,y;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
		d[x]++;
		d[y]++;
	}
	scanf("%s",s+1);
	topsort();
	for(x=1;x<=n;x++){
		if(!del[x])break;
	}
	if(x>n)
		putchar('0');
	else{
		dfs(0,x);
		sum-=2;
		printf("%d",sum+mn);
	}
}

巴特西

[ARC097F]Monochrome Cat

最新文章

热门文章