1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <bits/stdc++.h>
using namespace std;
const int N = 200010, M = N * 2;
int n;
int color[N];
int h[N], e[M], ne[M], idx;
int f[N]; // 1为根,f[i]表示以i为根的子树且包含i的连通块中白色减黑色的最大值
int dp[N]; // dp[i]表示整棵树以i为根....
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa) {
f[u] = color[u] ? 1 : -1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dfs(j, u);
f[u] += max(0, f[j]);
}
}
void dfs2(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dp[j] = f[j] + max(dp[u] - max(0, f[j]), 0);
dfs2(j, u);
}
}
int main() {
memset(h, -1, sizeof h);
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &color[i]);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1, -1);
dp[1] = f[1];
dfs2(1, -1);
for (int i = 1; i <= n; i++) printf("%d ", dp[i]);
return 0;
}
|