给定一棵有 n 个节点二叉树 T ,树上的每个点 i 有点权 ai 。
考虑二叉树下的先序遍历 t=v1,…,vn ,我们定义其平滑性为
D(t)=1≤i<n∑∣avi−avi+1∣现在,你可以交换任意节点的左右子树,使得树 T 的先序遍历的平滑性最小。
输入的第一行包含一个正整数 n(n≤2000) 。
输入的第二行包含 n 个正整数,第 i 个正整数 ai 为节点 i 的点权,保证 1≤ai≤109 。
输入的第三行包含 n−1 个正整数,第 i 个正整数 fi 为节点 i+1 的父节点,保证 1≤fi≤i 且每个 fi 不会出现超过 2 次。
我们约定 fi 第一次出现时,表示 i+1 是 fi 的左儿子, fi 第二次出现时,表示 i+1 是 fi 的右儿子。
输出一个非负整数,即所求的最小平滑性。
输入
5
1 2 3 4 5
1 1 2 2
输出
6
----------分割线------------
考场上的原数据n≤4e5 , 但是塔子哥还没有明确的解法。希望有大佬能提供标答
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.