CF1324F Maximum White Subtree—

换根dp，一般用来解决在无根树上，需要以每个节点为根跑一边dfs的dp问题

我们做两遍dfs

先钦定任意一个点为根

第一遍，算出\(f_i\)表示\(i\)的子树产生的答案，这里，子树指的是以我们钦定的那个点为根的有根树上的子树

这是从下向上的转移，也是一般树上dp的常规操作

第二遍，我们要算出真正的答案

这次是对于无根树中的子树，在第一遍dfs中，\(f_i\)已经包含了\(i\)所有“向下”的子树的贡献，那剩下的一棵子树是以它为根并向上连向它父亲的

设\(i\)的父亲是\(fa\)

这个子树的贡献是\(ans_{fa}\)减去节点\(i\)和它“向下”的子树对\(ans_{fa}\)的贡献（\(i\)的贡献已经在第一遍算进去了，所以这遍做的其实是以\(fa\)为根的计算）

也就是\(ans_{fa}-f_i\)

那么我们只需要将\(ans_i=f_i+ans_{fa}-f_i\)

上面那个式子看起来有点傻，但其中的-和+只是代表了将某些某些节点的贡献“去掉”和“加上”的方法，具体在每个题一般是不同的

当然\(+f_i\)和\(-f_i\)也不一定就能消掉（能消掉就不用换根dp了

这一遍是从上向下转移的过程

那么我们来看这个题

给定一棵\(n\)个节点无根树，每个节点有一个颜色，黑或白，黑色记为0，白色记为1

对于每个节点\(u\)，选出一个包含\(u\)的连通子图，设子图中白点个数为\(cnt_1\)，黑点个数为\(cnt_2\)，请最大化\(cnt_1 - cnt_2\)

我们再代码中将黑色记为-1，白色记为1

很显然:

\[f_i=a_i+\sum_{v\subset son_i}max(f_v,0)
\]

\(a_i\)就是\(i\)号点的颜色

那么可以根据上文的讲解得出:

\[ans_i=f_i+max(ans_{fa}-max(f_i,0),0)
\]

所以得出代码：

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline int read(){

	int x=0,y=1;

	char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

int n;

struct data{

	int cnt0,cnt1,ans;

};

int ans[200006],f[200006],a[200006];

int fir[200006],nex[400006],to[400006],tot;

inline void add(int x,int y){

	to[++tot]=y;

	nex[tot]=fir[x];fir[x]=tot;

}

void dfs1(int x,int fa){

	f[x]=a[x];

	for(reg int v,i=fir[x];i;i=nex[i]){

		v=to[i];

		if(v==fa) continue;

		dfs1(v,x);

		f[x]+=std::max(0,f[v]);

	}

}

void dfs2(int x,int fa){

	if(x!=1) ans[x]=std::max(ans[fa]-std::max(0,f[x]),0)+f[x];

	for(reg int i=fir[x];i;i=nex[i])if(to[i]!=fa) dfs2(to[i],x);

}

int main(){

	n=read();

	for(reg int i=1;i<=n;i++){

		a[i]=read();

		if(!a[i]) a[i]=-1;

	}

	for(reg int u,v,i=1;i<n;i++){

		u=read();v=read();

		add(u,v);add(v,u);

	}

	dfs1(1,1);

	ans[1]=f[1];dfs2(1,1);

	for(reg int i=1;i<=n;i++) std::printf("%d ",ans[i]);

	return 0;

}

巴特西

CF1324F Maximum White Subtree——换根dp

最新文章

热门文章