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