思路

集合 $S$ 内的点需要全连通，因此它们必属于同一棵树。反证：若它们属于两棵或以上的树，则必存在两个不同的树根，它们无法连通。

由于树根只有一个，因此可将所有方案按树根分成 $n$ 类，用 $f(u)$ 表示以 $u$ 为根的那类的最大和。

对于以 $u$ 为根构造的 $S$，$u$ 一定在集合中。对于 $u$ 的任意儿子 $s$，若 $S$ 想包含子树中的任何点，则必须包含子树的根，因此可直接考虑以 $s$ 为根的子集。若 $f(s) \le 0$，则将以 $s$ 为根的子集加入 $S$ 并不能使总和变大，甚至会变小，因此不能选择该子集。反之，若 $f(s) > 0$，则将以 $s$ 为根的子集加入 $S$ 可以使总和变大，因此需要选择它。

#include <cstring>
#include <iostream>

using namespace std;
using LL = long long;

const int N = 100010, M = N << 1, INF = 1e7;

int n;
int w[N], h[N], e[M], ne[M], idx;
LL ans = -INF;

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

LL dfs(int u, int p) {
  LL s = w[u];
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    if (j == p) continue;
    s += max(0LL, dfs(j, u));
  }
  ans = max(ans, s);
  return s;
}

int main() {
  memset(h, -1, sizeof h);

  cin >> n;
  for (int i = 1; i <= n; i++) cin >> w[i];
  for (int i = 0; i < n - 1; i++) {
    int a, b; cin >> a >> b;
    add(a, b), add(b, a);
  }

  dfs(1, -1);
  cout << ans << endl;

  return 0;
}