树形动态规划、二次扫描

使用 $a_i$ 表示节点 $i$ 的点权，将黑点的点权改为 $-1$，问题转化为对每个 $i$ 求树上包含 $i$ 的连通块的点权和的最大值。

指定 $1$ 为根节点，设计 $dp_i$ 为节点 $i$ 子树中包含 $i$ 的连通块的点权和的最大值，枚举子节点转移。

$$dp_i = a_i + \sum\limits_{j \in \operatorname{son}(i)} \max(dp_j,0)$$

通过第一次遍历可以得到节点 $1$ 的答案，接下来变更状态信息，$dp_i$ 表示树上包含节点 $i$ 的连通块的点权和的最大值，二次扫描更新 $dp_i$ 的值得到答案。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int n,a[200'005],dp[200'005],ans[200'005];
vector<int> v[200'005];
void dfs(int x,int las){
    dp[x]=a[x];
    for(int i:v[x]) if(i!=las){
        dfs(i,x);
        dp[x]+=max(dp[i],0);
    }
}
void tree(int x,int las){
    ans[x]=dp[x];
    for(int i:v[x]) if(i!=las){
        dp[x]-=max(dp[i],0);
        dp[i]+=max(dp[x],0);
        tree(i,x);
        dp[i]-=max(dp[x],0);
        dp[x]+=max(dp[i],0);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) if(a[i]==0) a[i]=-1;
    for(int i=1;i<=n-1;i++){
        static int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0),tree(1,0);
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}