题意

给定一棵\(n\)个节点的无根树，每个节点为黑色或者白色，每个点的答案为包含该点的子树（指无根子树）的白色节点数减黑色节点数的最大值

分析

对于无根树的题一般指定某一个点为根，不妨设为\(1\)

我们发现对于\(1\)号节点，他的某棵子树（将\(1\)视为根）如果白色节点数大于黑色节点数，则他的答案加上该差值

我们先采用树形\(DP\)将所有节点都这样统计一遍，这样就获得了来自子树的贡献

即\(a[i]\)为以\(i\)为根，所有白色节点数大于黑色节点数的子树的贡献

然后对于除\(1\)节点以外所有节点，还需要统计与父亲这一棵无向子树的关系

设遍历到\(now\)节点，子树节点为\(to\)节点

• \(a[to]>0\)，则\(now\)的答案子树包括\(to\)节点，\(to\)节点选择\(now\)的答案子树和\(to\)的答案子树中的最大值（因为已经包括，所以不是加和）

  \[a[to] = max(a[to], a[now])
  \]

• \(a[to]\leq0\)，则\(now\)的答案子树不包括\(to\)节点，\(to\)节点选择与\(now\)的答案子树进行拼接或不拼接的最大值（因为不包括，所以是加和）

  \[a[to] = max(a[to], a[now] + a[to])
  \]

  #pragma GCC optimize(3, "Ofast", "inline")

  #include

  #define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  #define ll long long
  #define int ll
  #define ls st<<1 #define rs st<<1|1 #define pii pair
  using namespace std;
  const int maxn = (ll) 3e5 + 5;
  const int mod = 1000000007;
  const int inf = 0x3f3f3f3f;
  vector v[maxn];
  int a[maxn];

  void dfs(int now, int pre) {
  for (auto &to:v[now]) {
  if (to == pre)
  continue;
  dfs(to, now);
  if (a[to] > 0)
  a[now] += a[to];
  }
  }

  void dfs2(int now, int pre) {
  for (auto &to:v[now]) {
  if (to == pre)
  continue;
  if (a[to] > 0)
  a[to] = max(a[to], a[now]);
  else
  a[to] = max(a[to], a[now] + a[to]);
  dfs2(to, now);
  }
  }

  signed main() {
  start;
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) { cin >> a[i];
  if (a[i] == 0)
  a[i] = -1;
  }
  for (int i = 1; i < n; ++i) { int x, y; cin >> x >> y;
  v[x].push_back(y);
  v[y].push_back(x);
  }
  dfs(1, 0);
  dfs2(1, 0);
  for (int i = 1; i <= n; ++i)
  cout << a[i] << ' ';
  return 0;
  }