不要什么脑子的带 \(log\) 做法。
思路
考虑 \(dp_{i,j}\) 表示红点到 \(i\)，蓝点到 \(j\) 的最大权值。
那么有：
\[dp_{i,j}=\max(dp_{fa_i,pre},dp_{fa_j,pre})+|a_i-a_j|
\]
其中 \(pre\) 是任意一个上一层节点。
发现第二维没有用。
可以优化：
\[dp_i=\max(dp_{fa_i}+\max(|a_i-a_{pre}|),dp_{pre}+|a_i-a_{pre}|)
\]
这样我们只需要维护 \(\max(|a_i-a_{pre}|)\) 与 \(\max(dp_{pre}+|a_i-a_{pre}|)\) 两个值即可。
直接树状数组维护。
Code
/**
* @file 1485E.cpp
* @author mfeitveer
* @date 2023-11-10
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)
typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;
bool ed;
const int N = 1000010;
const int mod = 998244353;
int n, m, q, cnt, fa[N], dep[N], head[N];
i64 a[N], b[N], dp[N];
vector<int> to[N];
struct edge { int to, nxt; } e[N * 2];
class Tree
{
int op, top{}, vis[N]{}, del[N]{}; i64 t[N];
inline int lb(int x)
{ return x & (-x); }
inline void Add(int x, i64 y)
{
if(!vis[x]) vis[x] = 1, del[++top] = x;
t[x] = max(t[x], y);
}
public:
inline Tree(int o) { op = o, memset(t, -0x3f, sizeof t); }
inline void add(int x, i64 y)
{ for(;(op==1 ? x <= m : x);x += lb(x) * op) Add(x, y); }
inline i64 ask(int x)
{
i64 r = -1e17;
for(;(op==1 ? x : x <= m);x += lb(x) * op * -1)
r = max(r, t[x]);
return r;
}
inline void clear()
{ while(top) vis[del[top]] = 0, t[del[top]] = -1e17, top--; }
} t1(-1), t2(1), t3(-1), t4(1);
inline void add(int x, int y)
{
e[++cnt] = {y, head[x]}, head[x] = cnt;
e[++cnt] = {x, head[y]}, head[y] = cnt;
}
inline void dfs(int now)
{
to[dep[now]].push_back(now), q = max(q, dep[now]);
for(int i = head[now];i;i = e[i].nxt)
{
if(e[i].to == fa[now]) continue;
dep[e[i].to] = dep[now] + 1, dfs(e[i].to);
}
}
inline void cmax(i64 &x, i64 y)
{ x = (y > x ? y : x); }
inline void solve()
{
cin >> n;
fro(i, 2, n) cin >> fa[i], add(i, fa[i]);
fro(i, 2, n) cin >> a[i], b[i - 1] = a[i];
sort(b + 1, b + n);
m = unique(b + 1, b + n) - b - 1;
fro(i, 2, n) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
dfs(1);
fro(i, 1, q)
{
for(auto j : to[i])
t1.add(a[j], b[a[j]]),
t2.add(a[j], -b[a[j]]);
for(auto j : to[i])
t3.add(a[j], dp[fa[j]] + b[a[j]]),
t4.add(a[j], dp[fa[j]] - b[a[j]]);
for(auto j : to[i])
{
cmax(dp[j], dp[fa[j]] - b[a[j]] + t1.ask(a[j]));
cmax(dp[j], dp[fa[j]] + b[a[j]] + t2.ask(a[j]));
cmax(dp[j], t3.ask(a[j]) - b[a[j]]);
cmax(dp[j], t4.ask(a[j]) + b[a[j]]);
}
t1.clear(), t2.clear(), t3.clear(), t4.clear();
}
i64 ans = 0;
for(auto i : to[q]) ans = max(ans, dp[i]);
cout << ans << "\n", cnt = q = 0;
fro(i, 1, n) dp[i] = head[i] = 0, to[i].clear();
}
bool st;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
double Mib = fabs((&ed-&st)/1048576.), Lim = 1024;
assert(Mib<=Lim), cerr << " Memory: " << Mib << "\n";
int t; cin >> t;
while(t--) solve();
return 0;
}