HDU 6662 Acesrc and Travel

树形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;
}
Last modification:August 16th, 2019 at 12:51 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment