Loading... 树形DP <!--more--> ## 2019 Multi-University Training Contest 8 08题 一道换根DP的题，当时没看出来，看出来也应该不会写hhh,看了[橘子猫](https://blog.csdn.net/ccsu_cat/article/details/99610296)的博客补的，相对于其他博客写得比较简短。 [ Acesrc and Travel](http://acm.hdu.edu.cn/showproblem.php?pid=6662) ### 思路： 首先任意选一个根，$dp[0][i]$表示$Zhang$选择i点出发(往子树叶子节点走)所能获得的最大的$\sum (a_i-b_i)$ ,$dp[1][i]$表示$Liu$选择i点出发所能获得的最小的$\sum (a_i-b_i)$ ,$dp[0][i]$表示$Zhang$在$i$点，则下一步就是$Liu$走，$Liu$肯定要获得最小的$\sum (a_i-b_i)$，因此$Liu$要走向$min(dp[1][son])$,$dp[1][i]$也是一个道理.由于走的过程是从根往叶子节点走，而树形DP是叶子走到根，其实这俩并不矛盾。 任意选根执行一遍后，我们得到了每个点往子树走的最优解，接下来我们就要换根了，从一个点出发的最优解可以是往父节点走，也可以往子树走(已经计算得出).设父节点$u$,子节点$v$。在进入$v$的时候，我们不希望父节点的答案是从自身转移过去的，这样就很麻烦,就不能直接利用父节点(这个时候就需要保存父节点的次大/小值，然后用这个更新$v$)。因此我们可以记录一下当前节点父节点的前缀最值和后缀最值，在即将进入$v$的过程中，我们使用前缀和后缀中的最值$mx$，这个$mx$表示的就是父节点的不走$v$的最优解，用这个$mx$我们可以更新$v$。这种方法就可以省去保存最大值，次大值等一些信息，个人感觉代码会相比好写一些。 具体可以看代码。 ### 代码 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; const ll inf = 1e15; typedef pair<ll, ll> P; vector<int> g[N]; vector<P> pre[N]; int a[N], b[N],n; ll dp[2][N],ans; void dfs1(int u, int fa) { dp[0][u] = inf, dp[1][u] = -inf; for (auto &v : g[u]){ if (v == fa) continue; dfs1(v, u); dp[0][u] = min(dp[0][u], dp[1][v]); dp[1][u] = max(dp[1][u], dp[0][v]); } if (dp[0][u] == inf) dp[0][u] = dp[1][u] = 0; dp[0][u] += a[u] - b[u]; dp[1][u] += a[u] - b[u]; } void dfs2(int u, int fa) { dp[0][u] = inf; dp[1][u] = -inf; for (auto &v : g[u]) { dp[0][u] = min(dp[0][u], dp[1][v]);//这里的更新的是真实答案，最值来自父节点和子树节点 dp[1][u] = max(dp[1][u], dp[0][v]); pre[u].push_back(P(dp[0][u], dp[1][u]));//前缀最值 } dp[0][u] += a[u] - b[u]; dp[1][u] += a[u] - b[u]; ans = max(ans, dp[0][u]);//这个是真实的答案，此时这个dp[0][u]已经无用，可以用来记录其他值 ll suf0 = inf, suf1 = -inf; for (int i = g[u].size() - 1; i >= 0; i--) { int v = g[u][i]; dp[0][u] = suf0, dp[1][u] = suf1; if (i){ dp[0][u] = min(dp[0][u], pre[u][i - 1].first); dp[1][u] = max(dp[1][u], pre[u][i - 1].second); } if (dp[0][u]== -inf) dp[0][u] = dp[1][u] = 0;//只有这一种情况会出现不更新 dp[0][u] += a[u] - b[u];//这个就是除了v的最优值，用来更新儿子，我使用了同一个数组 dp[1][u] += a[u] - b[u]; suf0 = min(suf0, dp[1][v]);//后缀最值 suf1 = max(suf1, dp[0][v]); if (v!=fa) dfs2(v, u); } } int main() { int _,x,y; scanf("%d", &_); while (_--) { scanf("%d", &n); for (int i = 1; i <= n; i++) g[i].clear(),pre[i].clear(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) scanf("%d", &b[i]); for (int i = 1; i < n; i++) { scanf("%d%d", &x, &y); g[x].push_back(y); g[y].push_back(x); } ans = -inf; dfs1(1, -1); dfs2(1, -1); printf("%lld\n", ans); } return 0; } ``` Last modification：August 16th, 2019 at 12:51 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
