Suppose we’ve got a special BST ( Binary Search Tree ), according to the definition, all the nodes in this BST has a bigger value than its left child and, at the same time, smaller than its right child.
On the other hand, every node in this special BST has a weight. For every node, its weight is smaller than either of its child.
If every value is different and so is the weight, we can get an interesting conclusion, when all weights and values of the nodes are determined, the BST is determined as well. Because such a tree can be seen as a BST inserted in the order of weight and sorted by value.
Another common sense, the depth of a node is defined by one plus its distance to the root. So the root’s depth is one.
Well, it seems that this special BST is not special enough, obviously. I mean it’s just a normal BST plus heap’s characteristics. So I made it a little bit more difficult, only a little bit, trust me.
When dealing with a real-life problem, the access frequency of each node differs, and I’ll set it on the node. We call the access cost of a node as its access frequency multiplies the depth of it, and the access cost of an entire special BST as the sum of all access cost of its nodes.
Now, I’ll give you a data set contains all nodes’ value, weight and access frequency, and you can modify the weight of some nodes, but every modify operation needs K extra cost. You can modify the weight to any real number, however, after that, every weight must still be different from each other. Your task is pretty simple, tell what the minimum sum of the access cost of this special BST and the extra cost is after the modify operations.