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: 6

💡 Note: Path from 0→3 is [0,1,3] with original cost 2+2+6=10. We can discount non-adjacent nodes 0 and 3 (prices 2→1 and 6→3), giving total cost 1+2+3=6.

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: 16

💡 Note: Trip 0→2 uses path [0,1,2], trip 1→3 uses path [1,3]. Node usage frequencies: node 0→1 time, node 1→2 times, node 2→1 time, node 3→1 time. Optimal discounting minimizes total cost to 16.

Example 3 — Linear Tree

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

› Output: 7

💡 Note: Path 0→2 is [0,1,2] with original cost 1+10+1=12. We can discount nodes 0 and 2 (non-adjacent), giving cost (1//2)+10+(1//2) = 0+10+0 = 10. Or discount just node 1: 1+(10//2)+1 = 1+5+1 = 7. Minimum is 7.

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

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

✓ Brute Force - Try All Discount Combinations

⏱️ Time: O(2ⁿ × n × trips) Space: O(n)

Generate all possible subsets of nodes that form an independent set (no adjacent nodes), apply discounts, and find the minimum total trip cost.

Dynamic Programming on Tree

⏱️ Time: O(n × trips + n) Space: O(n)

First count how many times each node is used across all trips, then use tree DP to find the optimal set of non-adjacent nodes to discount that minimizes total cost.

Brute Force - Try All Discount Combinations — Algorithm Steps

Build adjacency list from edges
Find all paths for each trip using DFS
Generate all valid independent sets of nodes
For each independent set, calculate total cost with discounts
Return minimum cost found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all possible combinations of nodes

Check Independence

Verify no two nodes in subset are adjacent

Calculate Cost

Find paths and compute total cost with discounts

Find Minimum

Track the lowest total cost found

Code -

solution.c — C

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

#define MAX_N 15
#define MAX_TRIPS 100
#define MAX_EDGES 100

int adj[MAX_N][MAX_N];
int adjCount[MAX_N];
int frequency[MAX_N];

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

void parseEdges(const char* str, int edges[][2], int* edgeCount) {
    *edgeCount = 0;
    const char* p = str;
    while (*p) {
        if (*p == '[' && *(p+1) != '[') {
            p++;
            edges[*edgeCount][0] = (int)strtol(p, (char**)&p, 10);
            while (*p == ',' || *p == ' ') p++;
            edges[*edgeCount][1] = (int)strtol(p, (char**)&p, 10);
            (*edgeCount)++;
        }
        p++;
    }
}

int findPath(int start, int end, int n, int visited[], int path[]) {
    if (start == end) {
        path[0] = start;
        return 1;
    }
    
    visited[start] = 1;
    for (int i = 0; i < adjCount[start]; i++) {
        int neighbor = adj[start][i];
        if (!visited[neighbor]) {
            int pathLen = findPath(neighbor, end, n, visited, path + 1);
            if (pathLen > 0) {
                path[0] = start;
                visited[start] = 0;
                return pathLen + 1;
            }
        }
    }
    visited[start] = 0;
    return 0;
}

int isIndependent(int subset[], int subsetSize) {
    for (int i = 0; i < subsetSize; i++) {
        int node = subset[i];
        for (int j = 0; j < adjCount[node]; j++) {
            int neighbor = adj[node][j];
            for (int k = 0; k < subsetSize; k++) {
                if (subset[k] == neighbor) return 0;
            }
        }
    }
    return 1;
}

int solution(int n, int edges[][2], int edgeCount, int price[], int trips[][2], int tripCount) {
    // Initialize
    for (int i = 0; i < n; i++) {
        adjCount[i] = 0;
        frequency[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 frequency of each node across all trips
    for (int t = 0; t < tripCount; t++) {
        int visited[MAX_N] = {0};
        int path[MAX_N];
        int pathLen = findPath(trips[t][0], trips[t][1], n, visited, path);
        for (int p = 0; p < pathLen; p++) {
            frequency[path[p]]++;
        }
    }
    
    int minCost = INT_MAX;
    
    // Try all possible subsets (including empty set)
    for (int mask = 0; mask < (1 << n); mask++) {
        int subset[MAX_N];
        int subsetSize = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset[subsetSize++] = i;
            }
        }
        
        if (isIndependent(subset, subsetSize)) {
            int totalCost = 0;
            
            // Calculate total cost with this discount set
            for (int node = 0; node < n; node++) {
                if (frequency[node] > 0) {
                    int nodeCost = price[node];
                    // Check if node is in discounted set
                    for (int s = 0; s < subsetSize; s++) {
                        if (subset[s] == node) {
                            nodeCost /= 2;
                            break;
                        }
                    }
                    totalCost += frequency[node] * nodeCost;
                }
            }
            
            if (totalCost < minCost) {
                minCost = totalCost;
            }
        }
    }
    
    return minCost;
}

int main() {
    int n;
    scanf("%d", &n);
    getchar();
    
    char line[1000];
    
    // Read edges
    fgets(line, sizeof(line), stdin);
    int edges[MAX_EDGES][2];
    int edgeCount;
    parseEdges(line, edges, &edgeCount);
    
    // Read price
    fgets(line, sizeof(line), stdin);
    int price[MAX_N];
    int priceCount;
    parseArray(line, price, &priceCount);
    
    // Read trips
    fgets(line, sizeof(line), stdin);
    int trips[MAX_TRIPS][2];
    int tripCount;
    parseEdges(line, trips, &tripCount);
    
    int result = solution(n, edges, edgeCount, price, trips, tripCount);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n × trips)

2^n possible subsets, each requiring n checks for adjacency and path cost calculation

✓ Linear Growth

Space Complexity

O(n)

Adjacency list and recursion stack for path finding

⚡ 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

Minimize the Total Price of the Trips - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Discount Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler