Minimize the Total Price of the Trips - Practice Coding Problems

Minimize the Total Price of the Trips - Problem

You are given an undirected tree with n nodes indexed from 0 to n-1. The tree is represented by a 2D integer array edges of length n-1, where edges[i] = [a_i, b_i] indicates an edge between nodes a_i and b_i.

Each node has an associated price given by the integer array price, where price[i] is the price of the i-th node. The price sum of a path is the sum of prices of all nodes on that path.

You are given a 2D integer array trips, where trips[i] = [start_i, end_i] represents a trip from node start_i to node end_i. Before performing any trips, you can choose some non-adjacent nodes and halve their prices.

Return the minimum total price sum to perform all the given trips.

Input & Output

Example 1 — Basic Tree with Single Trip

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

› Output: 11

💡 Note: Path from 0→3 is [0,1,3]. Original cost: 2+2+6=10. We can discount node 0 (price 2→1) and node 3 (price 6→3, not adjacent to 0). Total: 1+2+3=6. Wait, let me recalculate: discount nodes 0 and 3 gives cost 1+2+3=6, but we need to check if this is optimal among all valid discount combinations.

Example 2 — Multiple Trips

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

› Output: 23

💡 Note: Trip 0→2 uses path [0,1,2], trip 1→3 uses path [1,3]. Node usage: 0→1 time, 1→2 times, 2→1 time, 3→1 time. We can discount non-adjacent nodes optimally to minimize total cost.

Example 3 — Linear Tree

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

› Output: 6

💡 Note: Path 0→2 is [0,1,2]. Original cost: 1+10+1=12. We can discount nodes 0 and 2 (non-adjacent), giving cost: 0.5+10+0.5=11. But we can also discount just node 1 (middle node with highest price), giving cost: 1+5+1=7. Actually, discounting nodes 0 and 2 gives: 1+10+1=12, with discount: 0+10+0=10. Wait, integer division: (1//2)+(10)+(1//2) = 0+10+0 = 10. Hmm, let me recalculate properly.

Constraints

1 ≤ n ≤ 50
edges.length == n - 1
0 ≤ a_i, b_i ≤ n - 1
edges represents a valid tree
1 ≤ price[i] ≤ 1000
1 ≤ trips.length ≤ 100
0 ≤ start_i, end_i ≤ n - 1

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Undirected tree with node prices and trip routes

Count Usage

Find how often each node is used across all trips

Apply Discounts

Choose non-adjacent nodes to discount optimally

Calculate Cost

Sum up total cost for all trips with discounts

Key Takeaway

🎯 Key Insight: Use tree DP to optimally place discounts on non-adjacent nodes based on usage frequency

Asked in

G Google 15 a Amazon 12 M Microsoft 8

This problem combines tree traversal with dynamic programming optimization. The key insight is to first count node usage frequencies across all trips, then use tree DP to find the optimal set of non-adjacent nodes to discount. The tree DP approach runs in O(n × trips) time with O(n) space, much better than the brute force O(2^n) approach.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming on Tree	O(n × trips + n)	O(n)	Use tree DP to optimally choose discount nodes while respecting adjacency constraints
Brute Force - Try All Discount Combinations	O(2ⁿ × n × trips)	O(n)	Try every possible subset of non-adjacent nodes to discount and calculate minimum cost

Dynamic Programming on Tree — Algorithm Steps

Build adjacency list and find all trip paths
Count usage frequency for each node across all trips
Use tree DP with states: dp[node][0] = min cost if node not discounted, dp[node][1] = min cost if node discounted
For each node, decide whether to discount based on children's optimal choices
Return minimum of dp[root][0] and dp[root][1]

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Usage

Count how often each node appears in trip paths

Tree DP

For each node, calculate cost if discounted vs not discounted

Optimal Choice

Choose discount pattern that minimizes total cost

Result

Return minimum cost from root's DP states

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 50
int adj[MAX_N][MAX_N];
int adjCount[MAX_N];
int price[MAX_N];
int usage[MAX_N];

void findPath(int start, int end, int parent, int path[], int* pathLen) {
    if (start == end) {
        path[*pathLen] = start;
        (*pathLen)++;
        return;
    }
    
    path[*pathLen] = start;
    (*pathLen)++;
    
    for (int i = 0; i < adjCount[start]; i++) {
        int neighbor = adj[start][i];
        if (neighbor != parent) {
            int oldLen = *pathLen;
            findPath(neighbor, end, start, path, pathLen);
            if (path[*pathLen - 1] == end) {
                return; // Found path
            }
            *pathLen = oldLen; // Backtrack
        }
    }
    (*pathLen)--; // Remove current node
}

void treeDp(int node, int parent, int dp[]) {
    int baseCost = price[node] * usage[node];
    int discountCost = (price[node] / 2) * usage[node];
    
    int childrenNotDiscount = 0;
    int childrenCanDiscount = 0;
    
    for (int i = 0; i < adjCount[node]; i++) {
        int neighbor = adj[node][i];
        if (neighbor != parent) {
            int childDp[2];
            treeDp(neighbor, node, childDp);
            childrenNotDiscount += childDp[0];
            childrenCanDiscount += (childDp[0] < childDp[1]) ? childDp[0] : childDp[1];
        }
    }
    
    dp[0] = baseCost + childrenCanDiscount;
    dp[1] = discountCost + childrenNotDiscount;
}

int solution(int n, int edges[][2], int edgeCount, int priceArr[], int trips[][2], int tripCount) {
    // Initialize
    for (int i = 0; i < n; i++) {
        adjCount[i] = 0;
        price[i] = priceArr[i];
        usage[i] = 0;
    }
    
    // Build adjacency list
    for (int i = 0; i < edgeCount; i++) {
        int a = edges[i][0], b = edges[i][1];
        adj[a][adjCount[a]++] = b;
        adj[b][adjCount[b]++] = a;
    }
    
    // Count usage frequency
    for (int t = 0; t < tripCount; t++) {
        int path[MAX_N];
        int pathLen = 0;
        findPath(trips[t][0], trips[t][1], -1, path, &pathLen);
        for (int p = 0; p < pathLen; p++) {
            usage[path[p]]++;
        }
    }
    
    // Tree DP
    int result[2];
    treeDp(0, -1, result);
    
    return (result[0] < result[1]) ? result[0] : result[1];
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simplified input parsing for demo
    int edges[MAX_N][2], edgeCount = n - 1;
    int priceArr[MAX_N];
    int trips[10][2], tripCount = 1;
    
    for (int i = 0; i < edgeCount; i++) {
        scanf("%d %d", &edges[i][0], &edges[i][1]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &priceArr[i]);
    }
    for (int i = 0; i < tripCount; i++) {
        scanf("%d %d", &trips[i][0], &trips[i][1]);
    }
    
    int result = solution(n, edges, edgeCount, priceArr, trips, tripCount);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × trips + n)

Finding all paths takes O(n × trips), tree DP takes O(n) for each node

✓ Linear Growth

Space Complexity

O(n)

Adjacency list, DP arrays, and recursion stack depth

⚡ Linearithmic Space

26.3K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming on Tree — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler