CF1324F Maximum White Subtree

CF1324F Maximum White Subtree

题意

给定一棵 $n$ 个结点的树，每个点的颜色是黑白中的一种。对于每个结点 $u$，选出一棵包含点 $u$ 的连通子树，求其中白点数减去黑点数的最大值。

Sol

考虑白点赋权为 $1$，黑点赋权为 $-1$，那么问题转化为以每个点为根求最大子树和。

考虑换根 dp。首先求出以 $1$ 为根构建子树形态，令 $dp_u$ 表示以 $u$ 为根的子树内的最大子树和，dp 转移方程为

$dp_u = \sum_{v\in node} \max( dp_v,0 )$

然后令 $f_u$ 表示包含点 $u$ 的连通子树内白点数减去黑点数的最大值，显然 $f_1=dp_1$。我们考虑从 $u$ 为根转移到相邻结点 $v$ 为根，则对应发生改变的 $dp$ 值实际只有 $dp_u$ 即其父亲的值。那么我们考虑记录下转移前 $f_u$ 的答案，那么转移方程即

$f_v = dp_v + \max(f_u-\max(dp_v,0),0)$

最后 $f$ 值即所求。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e5+1e1;
const lint INF=1e18+1e9;

struct Edge{
	int nxt,to;
}e[MAXN<<1];
int head[MAXN],ans[MAXN],col[MAXN],sz[MAXN],fa[MAXN],n,tot;

void Addedge(int u,int v){
	e[++tot]=(Edge){head[u],v};
	head[u]=tot;
	return;
}

void Getsz(int u){
	sz[u]=(!col[u] ? -1 : 1);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(fa[u]==v) continue;
		fa[v]=u,Getsz(v);
		if(sz[v]>0) sz[u]+=sz[v];
	}
	return;
}

void Dfs(int u,int f){
	ans[u]=(fa[u] ? sz[u]+max(f-max(sz[u],0),0) : f);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(fa[u]!=v) Dfs(v,ans[u]);
	}
	return;
}

int main(void){

	scanf("%d",&n);
	for(int i=1;i<=n;i++) col[i]=readint;
	for(int i=1;i<n;i++){
		int u=readint,v=readint;
		Addedge(u,v),Addedge(v,u);
	}
	Getsz(1),Dfs(1,sz[1]);
	for(int i=1;i<=n;i++) printf("%d ",ans[i]);

	return 0;
}