Minimum Cost Escape in the Binary Tree Escape Room

Two friends, Xiao-Tu and Xiao-Fang, have agreed to try an escape room that is arranged as a complete binary tree with (n) nodes. Each node contains a light bulb with a weight (a_i) and each edge has a weight (b_i). To escape the room they must light all the bulbs. The rules are as follows:

1. The first bulb you light is free (cost 0).
2. When you light a new bulb (v) (after bulb (u) was lit immediately before), the cost incurred is (D_{u,v} \times a_v), where (D_{u,v}) is the distance between node (u) and node (v); the distance is the sum of the weights on the unique path between them.
3. At any moment during the process, all lit bulbs must form a connected subtree of the original tree.
4. Moreover, once you light a bulb, you must immediately light all bulbs in its subtree (i.e. all bulbs in the complete binary tree rooted at that node) before lighting any bulb outside that subtree.

It can be shown that under these rules the only valid lighting orders are those obtained by a depth-first traversal starting at the root (node 1), with the freedom to choose the order in which the two child subtrees are processed. Formally, if a node has two children then the DFS order can be either: ( [u, \text{DFS}(\text{left}), \text{DFS}(\text{right})] ) or ( [u, \text{DFS}(\text{right}), \text{DFS}(\text{left})] ).

Assume the tree is numbered from (1) to (n) in the usual way (with node (1) as root, and for each node (i), its left child is (2i) and its right child is (2i+1) if they exist). For every edge from a node (u) to its child (v), the cost to light (v) when coming from (u) is given by [ \text{cost}(u,v) = b_{v}\times a_v, ] and if the previous lit node is not the parent then the cost is the weighted distance along the unique path. For instance, if after finishing one subtree the next bulb to be lit is (w) (child of (u)) and the previously lit node from the processed subtree was (v), then the cost is [ \bigl(b(u,v)+\text{(additional distance)}+b(u,w)\bigr) \times a_w, ] where (b(u,v)) denotes the sum of the edge weights on the path from (u) to (v).

Your task is to compute the minimum total cost to light all the bulbs and escape the room. The input guarantees that the only valid order is the DFS order starting at node 1, with each node’s children processed consecutively, though the order between the left and right subtree at any node may be interchanged if it gives a lower total cost.

A hint for solving the problem is to use a recursive dynamic programming approach. For each node (u), let (dp[u]) be the minimum extra cost to light all bulbs in the subtree rooted at (u) given that (u) is lit. Also, let (end[u]) be the distance from (u) to the last lit bulb in the optimal ordering of its subtree. Then for a node with both children (v) and (w), one may compute two possible orders: [ \begin{aligned} &\text{Option 1 (left-first): } dp[u] = b_{v},a_v + dp[v] + (b_{v} + end[v] + b_{w}),a_w + dp[w], \ &\text{with } end[u] = b_{w} + end[w], \ &\text{Option 2 (right-first): } dp[u] = b_{w},a_w + dp[w] + (b_{w} + end[w] + b_{v}),a_v + dp[v], \ &\text{with } end[u] = b_{v} + end[v]. \end{aligned} ]

For a leaf node, (dp[u]=0) and (end[u]=0).

The answer to the problem is (dp[1]), computed recursively from the leaves up to the root.

inputFormat

The input is given in the following format:

(n)

(a_1\ a_2\ \ldots\ a_n)

(b_2\ b_3\ \ldots\ b_n)

Here, (n) is the number of nodes in the complete binary tree. The second line contains (n) integers representing the weight (a_i) for each bulb in node (i). The third line contains (n-1) integers where the (i)-th number represents the weight of the edge connecting node (\lfloor i/2 \rfloor) and node (i) (for (i=2,3,\dots,n)).

outputFormat

Output a single integer, which is the minimum total cost to light all the bulbs and escape the room.

sample

1
5

0