Maximum White Subtree

思路

如果考慮其覆蓋范圍只會(huì)到其子樹上，不會(huì)到其父節(jié)點(diǎn)上的話(假設(shè)的情況)，這道題就非常好寫了，就是一個(gè)簡單的自底向上傳遞的樹形$dp$。所以我們還要考慮的就是連接其父節(jié)點(diǎn)，因此我們只需要再進(jìn)行一個(gè)自頂下向傳遞的樹形$dp$即可。

第一遍的$dfs$比較簡單，但是第二遍的$dfs$有一些細(xì)節(jié)需要考慮，我在下面的代碼中給出了注釋。

寫完后找了題解，好像這是換根$dp?$，蒟蒻我沒有學(xué)過啥換根$dp$。

代碼

#include <bits/stdc++.h> #define mp make_pair #define pb push_backusing namespace std;typedef pair<int, int> pii; typedef long long ll; typedef unsigned long long ull;const double eps = 1e-7; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 2e5 + 10;int head[N], nex[N << 1], to[N << 1], cnt = 1; int dp[N], a[N], n;void add(int x, int y) {to[cnt] = y;nex[cnt] = head[x];head[x] = cnt++; }void dfs1(int rt, int fa) {if(a[rt] == 0) dp[rt] = -1;//設(shè)置dp數(shù)組的初值，這個(gè)應(yīng)該比較簡單理解。else dp[rt] = 1;for(int i = head[rt]; i; i = nex[i]) {if(to[i] == fa) continue;dfs1(to[i], rt);dp[rt] = max(dp[rt], dp[rt] + dp[to[i]]);//兩種選擇，與其子樹連接或者不連接。} }void dfs2(int rt, int fa) {for(int i = head[rt]; i; i = nex[i]) {if(to[i] == fa) continue;dp[to[i]] = max(dp[to[i]], dp[to[i]] + dp[rt] - max(dp[to[i]], 0));//這個(gè)的de[rt] - max(dp[to[i]], 0)，表示的意思是：如果這個(gè)節(jié)點(diǎn)在上一躺的dfs中選擇了這個(gè)兒子節(jié)點(diǎn)那么這個(gè)點(diǎn)一定是正數(shù)，如果這個(gè)點(diǎn)是負(fù)數(shù)，那么他在上一躺就沒有被選擇到，所以我們不需要減去這個(gè)點(diǎn)的值。dfs2(to[i], rt);} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read();for(int i = 1; i <= n; i++) a[i] = read();for(int i = 1; i < n; i++) {int x = read(), y = read();add(x, y);add(y, x);}dfs1(1, -1);dfs2(1, -1);for(int i = 1; i <= n; i++)printf("%d%c", dp[i], i == n ? '\n' : ' ');return 0; }

總結(jié)

以上是生活随笔為你收集整理的F：Maximum White Subtree（树形dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。