Codeforces Round #627 (Div. 3)F. Maximum White Subtree

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int M=2e5+5;
int ans[M],a[M];
vector<int>g[M];
int dfs1(int u,int fa){
    int tmp;
    if(a[u]==1)
        tmp=1;
    else
        tmp=-1;
    for(auto v:g[u]){
        if(v!=fa){
            int x=dfs1(v,u);
            tmp+=max(0,x);
        }
    }
    return ans[u]=tmp;
}
void dfs2(int u,int fa){
    if(fa!=0){
        int tmp=ans[fa];
        tmp-=max(0,ans[u]);
        ans[u]+=max(0,tmp);
    }
    for(auto v:g[u]){
        if(v!=fa)
            dfs2(v,u);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int u,v,i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}