树形DP

2019 Multi-University Training Contest 8 08题

一道换根DP的题，当时没看出来，看出来也应该不会写hhh,看了橘子猫的博客补的，相对于其他博客写得比较简短。

Acesrc and Travel

思路：

首先任意选一个根，$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$。这种方法就可以省去保存最大值，次大值等一些信息，个人感觉代码会相比好写一些。

具体可以看代码。

代码

#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;
}