Pruning the Tree: Branch Delivery Optimization

Daleva Geoge's garden features an unpruned tree that has become an eyesore. With guests arriving, he must trim the tree by removing extra branches from some donor leaf nodes and attaching them to other receiver leaf nodes to enhance the tree's appearance.

The tree is rooted at node \(1\) and consists of \(n\) nodes. There are \(S\) designated donor leaf nodes; the \(i\)-th donor leaf has \(a_i\) extra branches (i.e. surplus branches). Also, there are \(T\) designated receiver leaf nodes; the \(i\)-th receiver leaf requires \(b_i\) branches to complete its look.

Daleva Geoge will start at the root, traverse the tree to collect extra branches from donor leaves and then deliver them to receiver leaves. Each edge has a given length. However, his pocket can carry at most \(G\) branches at any time. After finishing his deliveries, he must return to the root.

You may assume that the total number of extra branches equals the total number of required branches, i.e., \(\sum_{i=1}^{S}a_i=\sum_{j=1}^{T}b_j\). A useful observation is that, for each subtree, if the net branch balance is \(x\) (positive means surplus; negative means deficit), then the cost incurred to transport the balance through an edge of length \(w\) to its parent is

\(2\times w\times \lceil \frac{|x|}{G} \rceil\).

Compute the minimum total distance that must be traversed in order to complete the pruning and branch delivery operation under these constraints.

inputFormat

The first line contains four integers \(n\), \(S\), \(T\), and \(G\) \((1 \leq n \leq 10^5,\ 1 \leq S, T \leq n,\ 1 \leq G \leq 10^9)\), representing the number of nodes in the tree, the number of donor leaves, the number of receiver leaves, and the maximum number of branches that can be carried at any time.

Each of the following \(n-1\) lines contains three integers \(u\), \(v\), and \(w\) \((1 \leq u,v \leq n,\ 1 \leq w \leq 10^4)\), indicating an undirected edge between nodes \(u\) and \(v\) with length \(w\). The tree is rooted at node \(1\).

The next line contains \(S\) distinct integers, indicating the indices of the donor leaf nodes.

The following line contains \(S\) integers \(a_1, a_2, \ldots, a_S\) \((1 \leq a_i \leq 10^5)\), where \(a_i\) is the number of extra branches at the corresponding donor leaf.

The next line contains \(T\) distinct integers, indicating the indices of the receiver leaf nodes.

The final line contains \(T\) integers \(b_1, b_2, \ldots, b_T\) \((1 \leq b_i \leq 10^5)\), where \(b_i\) is the number of branches required at the corresponding receiver leaf.

outputFormat

Output a single integer: the minimum total distance that must be traversed to complete the pruning and branch delivery task while never carrying more than \(G\) branches at any time and eventually returning to the root.

sample

5 1 1 2
1 2 3
1 3 2
3 4 4
3 5 6
2
5
4
5

18

</p>