思路：我们假设节点1为root，如果我们知道了root所有子树的最优情况，那么我们可以把1节点的最优情况传递给它的所有子树（当然如果传递给如图2的子树，那么需要把以2为root的最优贡献给减去，再传递root[1]的最优价值）。那我们这么维护子树的最优情况？很显然，如果子树的价值是负数，那么子树给父结点的价值应该是0，如果是正数，则可以把这个价值传递给父结点。
1 #include <iostream> 2 #include <deque> 3 #include <algorithm> 4 #include <stack> 5 #include <vector> 6 #include <cstring> 7 8 using namespace std; 9 10 const int N = 2e5 + 10; 11 12 struct Tree{ 13 int cnt; 14 bool white; 15 }tree[N]; 16 struct Edge{ 17 int to, nxt; 18 }e[N << 1]; 19 int head[N]; 20 int n, tot; 21 22 inline void add(int u, int v){ 23 e[tot].to = v; e[tot].nxt = head[u]; head[u] = tot++; 24 e[tot].to = u; e[tot].nxt = head[v]; head[v] = tot++; 25 } 26 27 int process(int now, int pre){ 28 int cnt = 0; 29 for(int o = head[now]; ~o; o = e[o].nxt){ 30 if(e[o].to != pre){ 31 cnt += process(e[o].to, now); 32 } 33 } 34 tree[now].cnt = tree[now].white ? 1 : -1; //自身是否是白色 35 tree[now].cnt += cnt > 0 ? cnt : 0; //子树给的价值 36 return max(tree[now].cnt, 0); //返回最优价值 37 } 38 39 void push_down(int now, int pre){ 40 for(int o = head[now]; ~o; o = e[o].nxt){ 41 if(e[o].to != pre){ 42 if(tree[now].cnt > 0){ //如果父结点价值为正，则传递价值 43 //如果该子树价值为正，则父结点传递的价值减去该子树传递的价值 44 //否则直接传递父结点的价值 45 if(tree[e[o].to].cnt > 0) tree[e[o].to].cnt += max(tree[now].cnt - tree[e[o].to].cnt, 0); 46 else tree[e[o].to].cnt += tree[now].cnt; 47 } 48 push_down(e[o].to, now); 49 } 50 } 51 } 52 53 void solve(){ 54 55 cin >> n; 56 for(int i = 1; i <= n; ++i) head[i] = -1; tot = 0; 57 for(int i = 1; i <= n; ++i){ 58 cin >> tree[i].white; 59 } 60 int u, v; 61 for(int i = 1; i < n; ++i){ 62 cin >> u >> v; 63 add(u, v); 64 } 65 process(1, 0); 66 push_down(1, 0); 67 for(int i = 1;i <= n; ++i) cout << tree[i].cnt << " "; 68 cout << endl; 69 } 70 71 int main(){ 72 73 ios::sync_with_stdio(false); 74 cin.tie(0); 75 cout.tie(0); 76 solve(); 77 78 return 0; 79 }