本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-30 12:15:59
题解思路：
设 $dp_{i,j}$ 代表：$i \to $ 蓝，$j \to $ 红，能到达状态最大值。
我们再枚举一个 $dp_{x , y}$，然后转移，时间复杂度就是 $\mathcal O(n ^ 4)$。
我们可以加入一些优化：
$dp_{x , y}$：
要么从 $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{f(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;
}
码字不易，求赞！
鲁ICP备2025150228号