<p>There exists an undirected and unrooted tree with <code>n</code> nodes indexed from <code>0</code> to <code>n - 1</code>. You are given the integer <code>n</code> and a 2D integer array <code>edges</code> of length <code>n - 1</code>, where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> in the tree.</p>

<p>Each node has an associated price. You are given an integer array <code>price</code>, where <code>price[i]</code> is the price of the <code>i<sup>th</sup></code> node.</p>

<p>The <strong>price sum</strong> of a given path is the sum of the prices of all nodes lying on that path.</p>

<p>Additionally, you are given a 2D integer array <code>trips</code>, where <code>trips[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> indicates that you start the <code>i<sup>th</sup></code> trip from the node <code>start<sub>i</sub></code> and travel to the node <code>end<sub>i</sub></code> by any path you like.</p>

<p>Before performing your first trip, you can choose some <strong>non-adjacent</strong> nodes and halve the prices.</p>

<p>Return <em>the minimum total price sum to perform all the given trips</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/03/16/diagram2.png" style="width: 541px; height: 181px;" />
<pre>
<strong>Input:</strong> n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
<strong>Output:</strong> 23
<strong>Explanation:</strong> 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 1<sup>st</sup> trip, we choose path [0,1,3]. The price sum of that path is 1 + 2 + 3 = 6.
For the 2<sup>nd</sup> trip, we choose path [2,1]. The price sum of that path is 2 + 5 = 7.
For the 3<sup>rd</sup> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/03/16/diagram3.png" style="width: 456px; height: 111px;" />
<pre>
<strong>Input:</strong> n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> 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 1<sup>st</sup> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 50</code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>edges</code> represents a valid tree.</li>
	<li><code>price.length == n</code></li>
	<li><code>price[i]</code> is an even integer.</li>
	<li><code>1 &lt;= price[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= trips.length &lt;= 100</code></li>
	<li><code>0 &lt;= start<sub>i</sub>, end<sub>i</sub>&nbsp;&lt;= n - 1</code></li>
</ul>

from collections import defaultdict

class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        # Step 1: Build the graph as an adjacency list
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # Step 2: Preprocess LCA using Binary Lifting (O(n log n))
        LOG = 16  # Since n <= 50, log2(50) is less than 6, but we use a bit more
        parent = [[-1] * LOG for _ in range(n)]
        depth = [0] * n

        def dfs_lca(node, par):
            for neighbor in graph[node]:
                if neighbor != par:
                    parent[neighbor][0] = node
                    depth[neighbor] = depth[node] + 1
                    dfs_lca(neighbor, node)

        def preprocess_lca(root=0):
            dfs_lca(root, -1)
            for i in range(1, LOG):
                for node in range(n):
                    if parent[node][i - 1] != -1:
                        parent[node][i] = parent[parent[node][i - 1]][i - 1]

        def lca(u, v):
            if depth[u] < depth[v]:
                u, v = v, u
            # Lift u to the same depth as v
            diff = depth[u] - depth[v]
            for i in range(LOG):
                if (diff >> i) & 1:
                    u = parent[u][i]
            if u == v:
                return u
            # Lift both u and v together
            for i in range(LOG - 1, -1, -1):
                if parent[u][i] != parent[v][i]:
                    u, v = parent[u][i], parent[v][i]
            return parent[u][0]

        preprocess_lca()

        # Step 3: Frequency calculation using a single DFS traversal
        freq = [0] * n
        
        def mark_path(u, v):
            ancestor = lca(u, v)
            # Increment path from u to ancestor
            cur = u
            while cur != ancestor:
                freq[cur] += 1
                cur = parent[cur][0]
            # Increment path from v to ancestor
            cur = v
            while cur != ancestor:
                freq[cur] += 1
                cur = parent[cur][0]
            # Increment the ancestor itself
            freq[ancestor] += 1

        for u, v in trips:
            mark_path(u, v)

        # Step 4: DFS-based dynamic programming to minimize the total price
        def dfs_dp(node, parent):
            # Without halving this node
            not_halved = freq[node] * price[node]
            # With halving this node
            halved = (freq[node] * price[node]) // 2

            for neighbor in graph[node]:
                if neighbor != parent:
                    child_not_halved, child_halved = dfs_dp(neighbor, node)
                    # If this node is not halved, we can choose to either halve or not halve the child
                    not_halved += min(child_not_halved, child_halved)
                    # If this node is halved, the child cannot be halved
                    halved += child_not_halved

            return not_halved, halved

        # Run DFS from any root (0 is arbitrary)
        result_not_halved, result_halved = dfs_dp(0, -1)

        # Return the minimum of halving or not halving the root node
        return min(result_not_halved, result_halved)

177