Maximum White Subtree

 题目的地址：https://vjudge.net/contest/363381#problem/f

参考题解：

https://blog.csdn.net/starlet_kiss/article/details/104844691

树状数组解法

https://www.cnblogs.com/cjtcalc/p/12485536.html

dfs解法

 

关于这道题，就是求最小连通子图的最优解，无根

综合上述两种方法，我的代码：

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxx=200100;
int edge[maxx<<1],eto[maxx<<1],head[maxx<<1];
int color[maxx],sum[maxx],ans[maxx],fu[maxx];
int tot=0,n;

int read(){
    /*
    int x=0,f=1;
    char s=getchar();
    while(s<0||s>9){if(s=='-'){f=-f;s=getchar();}}
    while(s>=0&&s<=9){x=x*10+s-'0';s=getchar();}
    return x*f;
    */
    char x=getchar();
    while(x==' '||x=='\n')x=getchar();//
    if(x=='0')      return -1;
    else if(x=='1') return 1;
    else            return 0;
}

void add(int u,int v){//eto到上一条以此节点为父节点的边，edge此节点的相邻结点
    eto[++tot]=head[u],edge[tot]=v,head[u]=tot;
}

void dfs(int u,int f){
    fu[u]=f;
    sum[u]=color[u];
    for(int i=head[u];i>0;i=eto[i]){
        int to=edge[i];
        if(to==f)continue;
        dfs(to,u);
        if(sum[to]>0)sum[u]+=sum[to];
    }
}

void dfs(int u,int f){
    if(sum[u]>=0)ans[u]=max(sum[u],ans[f]);
    else if(ans[f]>0)ans[u]=ans[f]+sum[u];
    else ans[u]=sum[u];
    for(int i=head[u];i>0;i=eto[i]){
        int to=edge[i];
        if(to==f)continue;
        dfs(to,u);
    }
}

int main(){
    scanf("%d",&n);
    memset(head,0,sizeof(head));//<string.h>
    for(int i=1;i<=n;i++){
        color[i]=read();
    }
    int a,b;
    for(int i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);//一条边存两次，所以需要两倍的空间
    }
    ans[0]=sum[0]=-1*maxx;
    dfs(1,0);
    ans[1]=sum[1];
    dfs(1,0);
    for(int i=1;i<=n;i++){printf("%d ",ans[i]);}
    printf("\n");
    return 0;
}