F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 1564. -- [NOI2009]二叉查找树

1564: [NOI2009]二叉查找树

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 950  Solved: 662
[Submit][Status][Discuss]

Description

Input

Output

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

Sample Input

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

Sample Output

29

HINT

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

Source

[Submit][Status][Discuss]

HOME Back