logo AlgoBeat OnlineJudge
登录 注册

#101564. [BZOJ 1564] [NOI2009]二叉查找树

内存限制:64 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

输入格式

输出格式

只有一个数字,即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。

样例

样例输入

4 10
1 2 3 4
1 2 3 4
1 2 3 4

样例输出

29

数据范围与提示

输入的原图是左图,它的访问代价是1×1+2×2+3×3+4×4=30。最佳的修改方案是把输入中的第3个结点的权值改成0,得到右图,访问代价是1×2+2×3+3×1+4×2=19,加上额外修改代价10,一共是29。