题解 | 遍历平滑线

import sys
sys.setrecursionlimit(1000000)

def main():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    a = [0] + a  # 节点编号从1开始，方便索引
    f = list(map(int, sys.stdin.readline().split()))
    
    # 构建二叉树结构：left[u] = 左孩子，right[u] = 右孩子
    left = [0] * (n + 1)
    right = [0] * (n + 1)
    child_count = [0] * (n + 1)  # 记录每个父节点已有的孩子数
    
    for i in range(n-1):
        child = i + 2  # 第i个元素对应节点i+2的父节点
        father = f[i]
        if child_count[father] == 0:
            left[father] = child  # 第一次出现是左孩子
        else:
            right[father] = child  # 第二次出现是右孩子
        child_count[father] += 1
    
    # 记忆化存储：dp[u] = (min_cost, last_val)
    memo = {}
    
    def dfs(u):
        if u == 0:  # 空节点
            return (0, 0)
        if u in memo:
            return memo[u]
        
        l = left[u]
        r = right[u]
        
        # 情况1：无左无右
        if l == 0 and r == 0:
            memo[u] = (0, a[u])
            return (0, a[u])
        
        # 情况2：只有左孩子
        elif r == 0:
            (cost_l, last_l) = dfs(l)
            total_cost = cost_l + abs(a[u] - a[l])
            memo[u] = (total_cost, last_l)
            return (total_cost, last_l)
        
        # 情况3：只有右孩子
        elif l == 0:
            (cost_r, last_r) = dfs(r)
            total_cost = cost_r + abs(a[u] - a[r])
            memo[u] = (total_cost, last_r)
            return (total_cost, last_r)
        
        # 情况4：有左有右，需要比较两种顺序
        else:
            # 获取左右子树的代价和最后节点值
            (cost_l, last_l) = dfs(l)
            (cost_r, last_r) = dfs(r)
            
            # 顺序1：根 → 左 → 右
            cost1 = cost_l + cost_r + abs(a[u] - a[l]) + abs(last_l - a[r])
            # 顺序2：根 → 右 → 左
            cost2 = cost_r + cost_l + abs(a[u] - a[r]) + abs(last_r - a[l])
            
            # 取较小的代价，并记录对应的最后节点值
            if cost1 <= cost2:
                min_cost = cost1
                final_last = last_r
            else:
                min_cost = cost2
                final_last = last_l
            
            memo[u] = (min_cost, final_last)
            return (min_cost, final_last)
    
    # 根节点是1，最终结果就是根节点的最小代价
    min_smooth = dfs(1)[0]
    print(min_smooth)

if __name__ == "__main__":
    main()