Choose some tree nodes to halve their prices so the total cost of all requested trips is minimized, while no two adjacent nodes are discounted together.
You are given an undirected tree with nodes labeled from $0n-1$. Each node has a positive integer price. You are also given a list of trips; each trip is a path between two nodes in the tree.
A node may be discounted by halving its price, but you cannot discount two adjacent nodes at the same time. Every time a trip passes through a node, that node's price contributes to the trip cost using its final price after any discount.
Return the minimum possible total cost of all trips after choosing a valid set of discounted nodes.
The key challenge is that each node may appear in many trips, so you must first determine how many times each node is used across all trip paths, then optimize the discount choices on the tree.
Input Format
- An integer representing the number of nodes.
- An array of undirected edges, where each edge connects two nodes.
- An array
priceof length whereprice[i]is the price of node . - An array of trips, where each trip is a pair
[start, end]describing a path in the tree.
Output Format
Return a single integer: the minimum total cost across all trips.
Constraints
- The graph is a tree with nodes.
- Each trip is between two valid nodes in the tree.
- Prices are positive integers.
- A node cannot be discounted if any of its adjacent nodes is discounted.
- The final answer fits in a 64-bit signed integer.
Example 1
Input
n = 4 edges = [[0,1],[1,2],[1,3]] price = [2,2,10,6] trips = [[0,2],[0,3]]
Output
12
Explanation
The trip 0->2 uses nodes 0,1,2 and the trip 0->3 uses nodes 0,1,3. A valid discount choice is to discount node 1 only, giving costs:
- node 0: 2 used twice = 4
- node 1: 1 used twice = 2
- node 2: 10 used once = 10
- node 3: 6 used once = 6 Total without discounting others is 22, but discounting node 2 instead of node 1 is not as good because node 2 appears only once. The minimum total is 12 after accounting for the optimal tree DP choices on all used nodes.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.