Minimize the Total Price of the Trips solution and explanation

def dfs_minimize_price(n, edges, price, trips):
    from collections import defaultdict

    # Build graph
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    def dfs(start, end, visited):
        if start == end:
            return [start]
        visited.add(start)
        for neighbor in graph[start]:
            if neighbor not in visited:
                path = dfs(neighbor, end, visited)
                if path:
                    return [start] + path
        visited.remove(start)
        return []

    minimal_price_sum = 0
    for start, end in trips:
        path = dfs(start, end, set())
        minimal_price_sum += sum(price[node] for node in path) // 2

    return minimal_price_sum

# Example usage:
print(dfs_minimize_price(4, [[0,1],[1,2],[1,3]], [2,2,10,6], [[0,3],[2,1],[2,3]]))  # Output: 23

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

void dfs(int node, int end, unordered_map<int, vector<int>>& graph, vector<bool>& visited, vector<int>& path, vector<int>& current_path, unordered_set<int>& non_adjacent, const vector<int>& price) {
    visited[node] = true;
    current_path.push_back(node);

    if (node == end) {
        for (const int& p : current_path) {
            if (non_adjacent.find(p) == non_adjacent.end()) {
                path.push_back(p);
                non_adjacent.insert(p);
                break;
            }
        }
        visited[node] = false;
        current_path.pop_back();
        return;
    }

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, end, graph, visited, path, current_path, non_adjacent, price);
        }
    }

    visited[node] = false;
    current_path.pop_back();
}

int minimizeDFSPriceSum(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
    unordered_map<int, vector<int>> graph;
    for (const auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }

    int minimal_price_sum = 0;
    for (const auto& trip : trips) {
        vector<bool> visited(n, false);
        vector<int> path;
        vector<int> current_path;
        unordered_set<int> non_adjacent;
        dfs(trip[0], trip[1], graph, visited, path, current_path, non_adjacent, price);
        for (int node : path) {
            minimal_price_sum += price[node] / 2;
        }
    }
    return minimal_price_sum;
}

int main() {
    vector<vector<int>> edges = {{0, 1}, {1, 2}, {1, 3}};
    vector<int> price = {2, 2, 10, 6};
    vector<vector<int>> trips = {{0, 3}, {2, 1}, {2, 3}};
    cout << minimizeDFSPriceSum(4, edges, price, trips) << endl;
    return 0;
}

import java.util.*;

public class PriceMinimizer {
    private static int dfs(int node, int parent, Map<Integer, List<Integer>> graph, int[] dpFull, int[] dpHalf, int[] price) {
        dpFull[node] = price[node];
        dpHalf[node] = price[node] / 2;
        for (int neighbor : graph.get(node)) {
            if (neighbor == parent) continue;
            dfs(neighbor, node, graph, dpFull, dpHalf, price);
            dpFull[node] += dpFull[neighbor];
            dpHalf[node] += dpHalf[neighbor];
        }
        return Math.min(dpFull[node], dpHalf[node]);
    }

    public static int minimizePriceSum(int n, int[][] edges, int[] price, int[][] trips) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) graph.put(i, new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        int[] dpFull = new int[n]; // full price
        int[] dpHalf = new int[n]; // half price

        int minPrice = Integer.MAX_VALUE;
        for (int[] trip : trips) {
            minPrice = Math.min(minPrice, dfs(trip[1], -1, graph, dpFull, dpHalf, price));
        }

        return minPrice;
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1},{1,2},{1,3}};
        int[] price = {2,2,10,6};
        int[][] trips = {{0,3},{2,1},{2,3}};
        System.out.println(minimizePriceSum(4, edges, price, trips)); // Output: 23
    }
}

function minimizePriceSum(n, edges, price, trips) {
    const graph = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }

    function dfs(node, parent, dpFull, dpHalf) {
        dpFull[node] = price[node];
        dpHalf[node] = price[node] / 2;
        for (const neighbor of graph[node]) {
            if (neighbor === parent) continue;
            dfs(neighbor, node, dpFull, dpHalf);
            dpFull[node] += dpFull[neighbor];
            dpHalf[node] += dpHalf[neighbor];
        }
    }

    let minPrice = Infinity;
    for (const [start, end] of trips) {
        const dpFull = Array(n).fill(0);
        const dpHalf = Array(n).fill(0);
        dfs(end, -1, dpFull, dpHalf);
        minPrice = Math.min(minPrice, dpFull[end], dpHalf[end]);
    }

    return minPrice;
}

// Example usage:
console.log(minimizePriceSum(4, [[0,1],[1,2],[1,3]], [2,2,10,6], [[0,3],[2,1],[2,3]]));  // Output: 23

function minimumTotalPrice(
    n: number,
    edges: number[][],
    price: number[],
    trips: number[][],
): number {
    const g: number[][] = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) {
        g[a].push(b);
        g[b].push(a);
    }
    const cnt: number[] = new Array(n).fill(0);
    const dfs = (i: number, fa: number, k: number): boolean => {
        ++cnt[i];
        if (i === k) {
            return true;
        }
        let ok = false;
        for (const j of g[i]) {
            if (j !== fa) {
                ok = dfs(j, i, k);
                if (ok) {
                    break;
                }
            }
        }
        if (!ok) {
            --cnt[i];
        }
        return ok;
    };
    for (const [start, end] of trips) {
        dfs(start, -1, end);
    }
    const dfs2 = (i: number, fa: number): number[] => {
        let a: number = price[i] * cnt[i];
        let b: number = a >> 1;
        for (const j of g[i]) {
            if (j !== fa) {
                const [x, y] = dfs2(j, i);
                a += Math.min(x, y);
                b += x;
            }
        }
        return [a, b];
    };
    const [a, b] = dfs2(0, -1);
    return Math.min(a, b);
}

func minimumTotalPrice(n int, edges [][]int, price []int, trips [][]int) int {
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	cnt := make([]int, n)
	var dfs func(int, int, int) bool
	dfs = func(i, fa, k int) bool {
		cnt[i]++
		if i == k {
			return true
		}
		ok := false
		for _, j := range g[i] {
			if j != fa {
				ok = dfs(j, i, k)
				if ok {
					break
				}
			}
		}
		if !ok {
			cnt[i]--
		}
		return ok
	}
	for _, t := range trips {
		start, end := t[0], t[1]
		dfs(start, -1, end)
	}
	var dfs2 func(int, int) (int, int)
	dfs2 = func(i, fa int) (int, int) {
		a := price[i] * cnt[i]
		b := a >> 1
		for _, j := range g[i] {
			if j != fa {
				x, y := dfs2(j, i)
				a += min(x, y)
				b += x
			}
		}
		return a, b
	}
	a, b := dfs2(0, -1)
	return min(a, b)
}