AT_arc097_d [ARC097F] Monochrome Cat 题解

模拟赛 T3 遇到，糖糖 DP。

思路分析：

考虑暴力的

O(n^2)

DP。定义

f_u

表示遍历以

u

为根的子树然后回到

fa_u

，

g_u

表示遍历后就不回来了（在子树内结束遍历），

t_u

表示

u

儿子个数，有如下转移：

f_u=\sum_{(u,v)\in E} f_v+(t_u+[c_u=W]+1)\bmod 2+2

g_u=\sum_{(u,v)\in E} f_v-\max_{(u,v)\in E}(f_v-g_v)+(\max(0,t_u-1)+[c_u=W]+1)\bmod 2 +1

发现有点问题，如果一颗子树内没有白点我们是可以不遍历的，于是定义

h_u

表示以

u

为根的子树中有多少给白点，如果

h_v=0

就不转移。

发现还有点问题，根节点在一开始不会被到达，所以直接特殊处理根节点:

f_{rt}=\sum_{({rt},v)\in E} f_v+(t_{rt}+[c_{rt}=W])\bmod 2

g_{rt}=\sum_{({rt},v)\in E} f_v-\max_{({rt},v)\in E}(f_v-g_v)+(\max(0,t_{rt}-1)+[c_{rt}=W])\bmod 2

还有一种办法是预先修改一次根的颜色（抵消我们认为其被到达的修改），然后求答案时把边的移动删掉。

发现上式结构还是相对简单的，直接换根即可，代码如下。

AC Code:

CPP

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+10;
int n,f[N],g[N],h[N],c[N],t[N],s[N],m2[N],m1[N],ans;
vector<int>e[N];
void dfs1(int u,int fa,int rt){
	h[u]=c[u];
	t[u]=0,s[u]=0,m2[u]=0,m1[u]=0;
	for(int v:e[u])if(v!=fa){
		dfs1(v,u,rt),h[u]+=h[v];if(h[v]==0)continue;
		t[u]++,s[u]+=f[v],m2[u]=max(m2[u],f[v]-g[v]);
		if(m2[u]>m1[u])swap(m2[u],m1[u]);
	}
	if(u==rt)
		f[u]=s[u]+((t[u]+c[u])&1),
		g[u]=s[u]-m1[u]+((t[u]-(t[u]>0)+c[u])&1);
	else
		f[u]=s[u]+((t[u]+c[u]+1)&1)+2,
		g[u]=s[u]-m1[u]+((t[u]-(t[u]>0)+c[u]+1)&1)+1;
}
void dfs2(int u,int fa){
	ans=min({ans,f[u],g[u]});
	for(int v:e[u])if(v!=fa){
		int fu=f[u],gu=g[u],hu=h[u],tu=t[u],su=s[u],m2u=m2[u],m1u=m1[u];
		int fv=f[v],gv=g[v],hv=h[v],tv=t[v],sv=s[v],m2v=m2[v],m1v=m1[v];
		if(h[v]>0){
			t[u]--,s[u]-=f[v];
			if(f[v]-g[v]==m1[u])swap(m1[u],m2[u]);
		}
		h[u]-=h[v],h[v]+=h[u];
		f[u]=s[u]+((t[u]+c[u]+1)&1)+2,
		g[u]=s[u]-m1[u]+((t[u]-(t[u]>0)+c[u]+1)&1)+1;
		if(h[u]>0){
			t[v]++,s[v]+=f[u],m2[v]=max(m2[v],f[u]-g[u]);
			if(m2[v]>m1[v])swap(m2[v],m1[v]);
		}
		f[v]=s[v]+((t[v]+c[v])&1),
		g[v]=s[v]-m1[v]+((t[v]-(t[v]>0)+c[v])&1);
		dfs2(v,u);
		f[u]=fu,g[u]=gu,h[u]=hu,t[u]=tu,s[u]=su,m2[u]=m2u,m1[u]=m1u;
		f[v]=fv,g[v]=gv,h[v]=hv,t[v]=tv,s[v]=sv,m2[v]=m2v,m1[v]=m1v;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1,u,v;i<n;i++)
		cin>>u>>v,e[u].pb(v),e[v].pb(u);
	string s;cin>>s;s=' '+s;
	for(int i=1;i<=n;i++)
		c[i]=(s[i]=='W');
	dfs1(1,0,1);
	ans=n*3;
	dfs2(1,0);
	cout<<ans;
	return 0;
}

完结撒花！！！

AT_arc097_d [ARC097F] Monochrome Cat 题解

文章操作

思路分析：

AC Code:

相关推荐

评论

AT_arc097_d [ARC097F] Monochrome Cat 题解