Maximum White Subtree
思路：我們假設節點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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/199353.html
標籤：其他
上一篇：9-爬樓梯
下一篇：【題解】債務