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;
}