本文章由 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;
}

码字不易，求赞！