#2646

Minimize the Total Price of the Trips

candidate master · 1485 · lc hard +32 · verified · 47.9% accepted · 517 likes · top 33%

Description

An undirected unrooted tree has n nodes indexed 0 to n - 1, each with an associated price. The path cost is the sum of node prices along the path. For each trip [starti, endi] in trips, you traverse the unique tree path between the two nodes. Before any trips begin, you may choose a set of non-adjacent nodes and halve their prices. Return the minimum total path cost across all trips.

Example 1:

Input: n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]

Output: 23

Explanation: The diagram above denotes the tree after rooting it at node 2. The first part shows the initial tree and the second part shows the tree after choosing nodes 0, 2, and 3, and making their price half.

For the 1st trip, we choose path [0,1,3]. The price sum of that path is 1 + 2 + 3 = 6.

For the 2nd trip, we choose path [2,1]. The price sum of that path is 2 + 5 = 7.

For the 3rd trip, we choose path [2,1,3]. The price sum of that path is 5 + 2 + 3 = 10.

The total price sum of all trips is 6 + 7 + 10 = 23.

It can be proven, that 23 is the minimum answer that we can achieve.

Example 2:

Input: n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]

Output: 1

Explanation: The diagram above denotes the tree after rooting it at node 0. The first part shows the initial tree and the second part shows the tree after choosing node 0, and making its price half.

For the 1st trip, we choose path [0]. The price sum of that path is 1.

The total price sum of all trips is 1. It can be proven, that 1 is the minimum answer that we can achieve.

Code

1

2

3

class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:

class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int: