CF1324F题解

题目大意

给出一颗$n$个节点的无根树，每个节点有一个颜色$a_u$，如果$a_u=0$则为黑色，否则为白色。

对于每个节点$u$，选出一个包含$u$的联通子图，设子图中白点个数为$cn{t}_1$，黑点个数为$cn{t}_2$，输出$cnt1-cn{t}_2$的最大值。

$1\le n\le 2\ast 10^5,0\le a_u\le 1$。

题目思路

先以$1$为根，预处理出每个点的子树中$cn{t}_1-cn{t}_2$的最大值。

然后进行换根$dp$。

当你把根从$u$转移到$v$时，$f{2}_v=\max (f{2}_u+f{1}_u-max(f{1}_v,0),0)$。

$f1$就是上面预处理的数组，$f_2$就是每个点子树外$cn{t}_1-cn{t}_2$的最大值。

因为只有根是必选的，所以其他值需要跟$0$取$max$。

具体实现参考代码。

#include
using namespace std;
const int N=200000+10;
int n,a[N],f1[N],f2[N];
int head[N<<1],nxt[N<<1],to[N<<1],tot=0;
void add(int u,int v)
{
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }   
    while(ch>='0'&&ch<='9')
        s=s*10+(ch-'0'),ch=getchar();
    return s*w;
}
void dfs1(int u,int fa)
{
    if(a[u])
        f1[u]=1;
    else    
        f1[u]=-1;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa)
            continue;
        dfs1(v,u);
        f1[u]+=max(f1[v],0);
    }
}
void dfs2(int u,int fa)
{
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa)
            continue;
        f2[v]=max(f2[u]+f1[u]-max(f1[v],0),0);
        dfs2(v,u);
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    for(int i=1;i<=n-1;++i)
    {
        int u=read(),v=read();
        add(u,v);
        add(v,u);
    }   
    dfs1(1,1);
    dfs2(1,1);
    for(int i=1;i<=n;++i)
        printf("%d ",f1[i]+f2[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68