CF1324F题解

DDream白日梦 / 2023-08-15 / 原文

CF1324F题解

题目描述

给定一棵 \(n\) 个节点无根树，每个节点 \(u\) 有一个颜色 \(a_u\)，若 \(a_u\) 为 \(0\) 则 \(u\) 是黑点，若 \(a_u\) 为 \(1\) 则 \(u\) 是白点。
对于每个节点 \(u\)，选出一个包含 \(u\) 的连通子图，设子图中白点个数为 \(cnt_1\)，黑点个数为 \(cnt_2\)，请最大化 \(cnt_1 - cnt_2\)。并输出这个值。
\(1 \leq n \leq 2 \times 10^5\)，\(0 \leq a_u \leq 1\)。

题解

本题为换根dp的模板题。为什么需要换根dp呢？原因是普通的dp只能维护节点子树类的信息。

对于此题，我们考虑一种朴素的求解方式，对于每个节点，枚举其作为根结点。令 \(dp[x]\) 为在节点 \(x\) 的子树内，包含 \(x\) 的连通子图的答案最大值，转移只需枚举产生正贡献的儿子即可。但是显然，这样的复杂度是爆炸的。

我们考虑换根dp。按照dfs序遍历每个节点为根节点的情况，我们不难发现，每次换根，只会改变交换的两节点的 \(dp\) 值，暴力修改即可。复杂度线性。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,a[N],dp[N],ans[N];
vector<int>edge[N];
void dfs1(int x,int fa)
{
	if(a[x]==1)
	dp[x]++;
	else
	dp[x]--;
	for(int i=0;i<edge[x].size();i++)
	{
		int to=edge[x][i];
		if(to==fa)
		continue;
		dfs1(to,x);
		if(dp[to]>0)
		dp[x]+=dp[to];
	}
	return;
}
void dfs2(int x,int fa)
{
	for(int i=0;i<edge[x].size();i++)
	{
		int to=edge[x][i];
		if(to==fa)
		continue;
		int xx=dp[to],xxx=dp[x];
		if(dp[to]>0)
		dp[x]-=dp[to];
		if(dp[x]>0)
		dp[to]+=dp[x];
		ans[to]=dp[to];
		dfs2(to,x);
		dp[to]=xx;
		dp[x]=xxx;
	}
	return;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs1(1,0);
	ans[1]=dp[1];
	dfs2(1,0);
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<" ";
	}
	return 0;
}