<p>You are given an integer <code>n</code> representing the number of nodes in a <strong>perfect binary tree</strong> consisting of nodes numbered from <code>1</code> to <code>n</code>. The root of the tree is node <code>1</code> and each node <code>i</code> in the tree has two children where the left child is the node <code>2 * i</code> and the right child is <code>2 * i + 1</code>.</p>

<p>Each node in the tree also has a <strong>cost</strong> represented by a given <strong>0-indexed</strong> integer array <code>cost</code> of size <code>n</code> where <code>cost[i]</code> is the cost of node <code>i + 1</code>. You are allowed to <strong>increment</strong> the cost of <strong>any</strong> node by <code>1</code> <strong>any</strong> number of times.</p>

<p>Return <em>the <strong>minimum</strong> number of increments you need to make the cost of paths from the root to each <strong>leaf</strong> node equal</em>.</p>

<p><strong>Note</strong>:</p>

<ul>
	<li>A <strong>perfect binary tree </strong>is a tree where each node, except the leaf nodes, has exactly 2 children.</li>
	<li>The <strong>cost of a path</strong> is the sum of costs of nodes in the path.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/04/04/binaryytreeedrawio-4.png" />
<pre>
<strong>Input:</strong> n = 7, cost = [1,5,2,2,3,3,1]
<strong>Output:</strong> 6
<strong>Explanation:</strong> We can do the following increments:
- Increase the cost of node 4 one time.
- Increase the cost of node 3 three times.
- Increase the cost of node 7 two times.
Each path from the root to a leaf will have a total cost of 9.
The total increments we did is 1 + 3 + 2 = 6.
It can be shown that this is the minimum answer we can achieve.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/04/04/binaryytreee2drawio.png" style="width: 205px; height: 151px;" />
<pre>
<strong>Input:</strong> n = 3, cost = [5,3,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong> The two paths already have equal total costs, so no increments are needed.
</pre>

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

<ul>
	<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>n + 1</code> is a power of <code>2</code></li>
	<li><code>cost.length == n</code></li>
	<li><code>1 &lt;= cost[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        # First, a perfect binary tree has the node number of 2^n - 1 (because the node number is 2^0 + 2^1 + ... + 2^n)
        # Second, each path has the same number of nodes.
        # 1. For the root node, we do not need to adjust because changing its value will impact all the paths.
        # 2. Since an operation can only increment the cost of node, the path cost is non-decreasing. That means, we have to take the maximum path cost as the base line.
        # 3. We must take the maximum path cost as the baseline. If a solution makes the path cost as M which is strictly greater than the maximum path cost, then it means for all paths, there is a node in the path that has been incremented. Then we can optimize the solution by reverting the changed node.
        # We can maintain a segment tree for the maximum path cost. We do a DFS to construct the tree. If a node is less than the maximum path cost, we can add it up by the diff. The diff should also be propagated to the children, but we can do lazy propagation to reduce the number of updates to the children nodes.
        tree = [0] * (n + 1)
        delta = [0] * (n + 1)

        def dfs(node, prefix):
            prefix += cost[node - 1]
            if (node << 1) > n:
                # This is a leaf node
                tree[node] = prefix
                return
            # This is non-leaf node
            dfs(node << 1, prefix)
            dfs((node << 1) + 1, prefix)
            tree[node] = max(tree[node << 1], tree[(node << 1) + 1])

        dfs(1, 0)

        # Traverse the segment tree and increment the nodes
        # Apparently, the maximum path cost is tree[1].
        ans = 0
        for i in range(2, n + 1):
            cur = tree[i] + delta[i]
            if cur < tree[1]:
                dt = tree[1] - cur
                delta[i] += dt
                ans += dt
            if delta[i] > 0 and (i << 1) < n:
                delta[i << 1] += delta[i]
                delta[(i << 1) + 1] += delta[i]
        return ans

1237