Minimum Tax Path in a Tree

You are given a city's road network, which forms an unrooted, undirected tree with n toll plazas (nodes), numbered 0 to n-1. Each plaza i has a tax[i]. The roads are given by a 2D array path.

You are also given a list of journeys, where each journey is a trip from a start node to an end node. The total tax for a single journey is the sum of taxes of all nodes on the unique simple path between the start and end nodes.

Before starting any journeys, you have a one-time opportunity to reduce costs. You can select any set of nodes to receive a discount, with one critical constraint: no two selected nodes can be adjacent. For every node you select, its tax is permanently halved (integer division).

Your task is to strategically choose the set of non-adjacent nodes for the tax discount to minimize the sum of total taxes over all given journeys.

Input Format:

The first line contains an integer n, the number of nodes.

The second line contains n space-separated integers, representing the tax array.

The third line contains n-1, the number of edges.

The next n-1 lines each contain two space-separated integers, u and v, representing a road.

The next line contains an integer q, the number of journeys.

The next q lines each contain two space-separated integers, start and end, for a journey.

Output Format:

Print a single integer representing the minimum possible sum of taxes across all journeys.