Minimum Tax Path in a Tree

Ninja

0/200

0 upvote

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

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

Sample Output 1:

Explanation for Sample 1:

- Path Analysis: The tree is a star graph with center 0. The only journey is from node 1 to node 2, so the path taken is `1 -> 0 -> 2`.
- Node Frequencies: The nodes on this path (`0`, `1`, `2`) are each visited once. Node `3` is not visited.
- Initial Total Tax: `tax[0]*1 + tax[1]*1 + tax[2]*1 + tax[3]*0` = `10 + 10 + 10 + 0 = 30`.
- Potential Savings: The potential saving for halving a node's tax is `(tax[i]/2) * frequency[i]`.
- Node 0: `(10/2) * 1 = 5`
- Node 1: `(10/2) * 1 = 5`
- Node 2: `(10/2) * 1 = 5`
- Node 3: `(10/2) * 0 = 0`
- Optimal Discount: We must select a set of non-adjacent nodes to maximize savings.
- Option A: Discount only the center node `0`. Savings = `5`.
- Option B: Discount the leaf nodes. The set of leaves `{1, 2, 3}` are all non-adjacent to each other. Total savings = `savings[1] + savings[2] + savings[3]` = `5 + 5 + 0 = 10`.
- The maximum possible saving is `10`.
- Minimum Final Tax: `Initial Tax - Max Savings` = `30 - 10 = 20`.

Expected Time Complexity:

The expected time complexity is O(N log N + Q log N).

Constraints:

1 <= n, q <= 10^5
1 <= tax[i] <= 1000
0 <= u, v < n

Time limit: 2 sec

Approaches (1)

Approach 1

Dynamic Programming

Time Complexity

Space Complexity

(100% EXP penalty)

Minimum Tax Path in a Tree

Console