CF1485E题解

· · 题解

题解思路：

设 dp_{i,j} 代表：i \to 蓝，j \to 红，能到达状态最大值。

我们再枚举一个 dp_{x , y}，然后转移，时间复杂度就是 \mathcal O(n ^ 4)。

我们可以加入一些优化：

要么从 $dp_{i , fa_{y}}$ 转移来。 要么从 $dp_{i , fa_{x}}$ 转移来。 这样的话就不用枚举 $j$ 了，时间复杂度变成了 $\mathcal O(n ^ 3)$。 我们发现直接一维就可以了，因为蓝色这个点可以在任意位置，所以我们只要知道层数就可以了，而红色点和蓝色点在同一层，所以只保留红色点那一维就可以了。 装态转移方程： > $1$ 操作 >> $dp_{y} = \max (dp_{y}, dp_{fa_{y}} + \operatorname{abs} (a_{y} - mi))$ 其中 $mi$ 表示这一层的最小值。 >> $dp_{y} = \max (dp_{y}, dp_{fa_{y}} + \operatorname{abs} (a_{y} - ma))$ 其中 $ma$ 表示这一层的最大值。 > $2$ 操作 >> $dp_{y} = \max (dp_{y} + dp_{fa_{x}} + \operatorname{abs} (a_{x} - a_{y}))$。 优化完之后时间复杂度就变成了 $\mathcal O(n ^ 2)$。 我们在做一个优化，这个优化只能优化二式： > 先把绝对值去掉： >> 要么是：$dp_{y} = \max (dp_{y}, dp_{fa_{x}} + a_{y} - a_{x})$。 >> 要么是：$dp_{y} = \max (dp_{y}, dp_{fa_{x}} + a_{x} - a_{y})$。 > 再把 $dp_{fa_{x}}$ 给提出来，那么我们只需要关心两个值就可以了，我们定义两个值： >> $f(x) = dp_{fa_{x}} - a_{x}
g(x) = dp_{fa_{x}} + a_{x}

那么我们就只需要记录 f(x),g(x) 的最大值就可以了，我们就在转移时直接用就可以了。

状态转移变为：

$dp_{y} = \max (dp_{y}, - a_{y} + \max{g(x)})$。

时间复杂度就变成了：\mathcal{O(n)}。

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 200010;
int n;
ll dp[N];
vector <int> e[N] , d[N];
int fa[N] , deep[N] , ma[N] , mi[N] , a[N];
void dfs (int u , int pre) {
    deep[u] = deep[pre] + 1;//深度，他的深度为他的父节点的深度加一
    d[deep[u]].push_back (u);//每一层有那些值
    ma[deep[u]] = max (ma[deep[u]] , a[u]);//每一层的最大值
    mi[deep[u]] = min (mi[deep[u]] , a[u]);//每一层的最小值
    for (auto v : e[u]) {
        if (v == pre) continue;
        fa[v] = u;//预处理fa数组
        dfs (v , u);//递归他的儿子节点
    }
}
void init () {//初始化
    for (int i = 1; i <= n; ++ i) {
        e[i].clear ();
        d[i].clear ();
        dp[i] = fa[i] = deep[i] = ma[i] = 0;
        mi[i] = 2e9;
    }
}
int main() {
    memset (mi , 0x3f , sizeof (mi));
    int T;
    scanf ("%d" , &T);
    while (T --) {
        init ();
        scanf ("%d" , &n);
        for (int i = 2; i <= n; ++ i) {
            int x;
            scanf ("%d" , &x);
            e[x].push_back (i);//连边
            e[i].push_back (x);
        }
        for (int i = 2; i <= n; ++ i) scanf ("%d" , &a[i]);
        dfs (1 , 1);//预处理
        ll ans = 0;
        for (int i = 2; i <= n; ++ i) {
            ll val1 = 0 , val2 = -2e9;//初始化
            for (auto x : d[i]) {//就是预处理f,g
                val1 = max (val1 , dp[fa[x]] + a[x]);
                val2 = max (val2 , dp[fa[x]] - a[x]);
            }
            for (auto x : d[i]) {
                dp[x] = max (dp[x] , dp[fa[x]] + max (ma[i] - a[x] , a[x] - mi[i]));//第一个转移方程 
                dp[x] = max (dp[x] , max (val1 - a[x] , val2 + a[x]));//第二个 
                ans = max (ans , dp[x]);//求个最大值 
            }
        }
        printf ("%lld\n" , ans);//输出
    }
    return 0;
}

码字不易，求赞！