<p>There is an undirected tree with <code>n</code> nodes labeled 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] = [u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>]</code> indicates that there is an edge between nodes <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> with weight <code>w<sub>i</sub></code> in the tree.</p>

<p>You are also given a 2D integer array <code>queries</code> of length <code>m</code>, where <code>queries[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>. For each query, find the <strong>minimum number of operations</strong> required to make the weight of every edge on the path from <code>a<sub>i</sub></code> to <code>b<sub>i</sub></code> equal. In one operation, you can choose any edge of the tree and change its weight to any value.</p>

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

<ul>
	<li>Queries are <strong>independent</strong> of each other, meaning that the tree returns to its <strong>initial state</strong> on each new query.</li>
	<li>The path from <code>a<sub>i</sub></code> to <code>b<sub>i</sub></code> is a sequence of <strong>distinct</strong> nodes starting with node <code>a<sub>i</sub></code> and ending with node <code>b<sub>i</sub></code> such that every two adjacent nodes in the sequence share an edge in the tree.</li>
</ul>

<p>Return <em>an array </em><code>answer</code><em> of length </em><code>m</code><em> where</em> <code>answer[i]</code> <em>is the answer to the</em> <code>i<sup>th</sup></code> <em>query.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/08/11/graph-6-1.png" style="width: 339px; height: 344px;" />
<pre>
<strong>Input:</strong> n = 7, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]], queries = [[0,3],[3,6],[2,6],[0,6]]
<strong>Output:</strong> [0,0,1,3]
<strong>Explanation:</strong> In the first query, all the edges in the path from 0 to 3 have a weight of 1. Hence, the answer is 0.
In the second query, all the edges in the path from 3 to 6 have a weight of 2. Hence, the answer is 0.
In the third query, we change the weight of edge [2,3] to 2. After this operation, all the edges in the path from 2 to 6 have a weight of 2. Hence, the answer is 1.
In the fourth query, we change the weights of edges [0,1], [1,2] and [2,3] to 2. After these operations, all the edges in the path from 0 to 6 have a weight of 2. Hence, the answer is 3.
For each queries[i], it can be shown that answer[i] is the minimum number of operations needed to equalize all the edge weights in the path from a<sub>i</sub> to b<sub>i</sub>.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/08/11/graph-9-1.png" style="width: 472px; height: 370px;" />
<pre>
<strong>Input:</strong> n = 8, edges = [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]], queries = [[4,6],[0,4],[6,5],[7,4]]
<strong>Output:</strong> [1,2,2,3]
<strong>Explanation:</strong> In the first query, we change the weight of edge [1,3] to 6. After this operation, all the edges in the path from 4 to 6 have a weight of 6. Hence, the answer is 1.
In the second query, we change the weight of edges [0,3] and [3,1] to 6. After these operations, all the edges in the path from 0 to 4 have a weight of 6. Hence, the answer is 2.
In the third query, we change the weight of edges [1,3] and [5,2] to 6. After these operations, all the edges in the path from 6 to 5 have a weight of 6. Hence, the answer is 2.
In the fourth query, we change the weights of edges [0,7], [0,3] and [1,3] to 6. After these operations, all the edges in the path from 7 to 4 have a weight of 6. Hence, the answer is 3.
For each queries[i], it can be shown that answer[i] is the minimum number of operations needed to equalize all the edge weights in the path from a<sub>i</sub> to b<sub>i</sub>.
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt; n</code></li>
	<li><code>1 &lt;= w<sub>i</sub> &lt;= 26</code></li>
	<li>The input is generated such that <code>edges</code> represents a valid tree.</li>
	<li><code>1 &lt;= queries.length == m &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>
</ul>

class Solution:
    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        """
        Use binary lifting for LCA finding.
        Then apply LCA equation: the frequency of edge weight w from a to b can be found as:
        weightCount[a][w] + weightCount[b][w] - 2 * weightCount[lca(a, b)][w]
        """
        adj = defaultdict(set)
        for u, v, w in edges:
            adj[u].add((v, w))
            adj[v].add((u, w))

        nb = n.bit_length() # Size of binary lifting table.

        # parent[power][i] = the ancestor that is 2^power levels up from i, at most 2**nb levels 
        parent = [ [0] * n for _ in range(nb) ]
        parent_weight = [0] * n  # parent_weight[i] = the weight from i to its immediate parent at parent[0][i]
        depth = [0] * n # Records the depth of each node

        def dfs(node, d):
            # Build base cases of binary lifting table, O(V+E) time
            depth[node] = d
            for child, w in adj[node]:
                parent[0][child] = node
                parent_weight[child] = w
                adj[child].remove((node, w)) # Avoids cycles
                dfs(child, d+1)
        dfs(0, 0)

        # Build complete binary lifting table O(NlogN)
        for i in range(1, nb):
            for j in range(n):
                # Parent of node j for this level i = parent of its parent from last level i-1
                parent[i][j] = parent[i-1][ parent[i-1][j] ]

        def find_parent(node, k):
            # Find node kth level up from it.
            # E.g., k = 7, b0111, queries: a = parent[0][node], b = parent[1][a], res = parent[2][b]
            res = node
            for i in range(nb):
                if (k & (1 << i)) != 0:
                    res = parent[i][res]
            return res

        @cache
        def lca(a, b): # O(logN) time
            if depth[a] < depth[b]:
                a, b = b, a # a must be larger or equal depth
            # Jump to the same level as b
            a = find_parent(a, depth[a] - depth[b])
            if a == b: # Found LCA
                return a
            # Otherwise, need to start from max possible jump to find LCA
            for i in reversed(range(nb)):
                if parent[i][a] != parent[i][b]: 
                    # Not equal means we can jump 2**i level up, next level to jump will be smaller
                    a = parent[i][a]
                    b = parent[i][b]
            return parent[0][a]

        @cache
        def count_weight(node, weight):
            """Counts # of weight values for node on the path from it to root"""
            if node == 0: return 0 # No node has label 0, so 0 means no more parent
            return count_weight(parent[0][node], weight) + (1 if parent_weight[node] == weight else 0)

        res = []
        for a, b in queries: # O(Q*26*inner_cost) time
            num_op = inf
            for w in range(1, 27):
                # Loops all possible weights and take the min value, which is the most freq weight
                num_op = min(
                    num_op,
                    # number of edges from a to b = depth[a] + depth[b] - 2 * depth[lca(a, b)]
                    # number of edges with weight w from a to b = \
                    # weightCount(a, w) + weightCount(b, w) - 2 * weightCount(lca(a, b), w)
                    depth[a] + depth[b] - 2 * depth[lca(a, b)] - (count_weight(a, w) + count_weight(b, w) - 2 * count_weight(lca(a, b), w)),
                )
            res.append(num_op)
        return res

72000