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

GraphT = List[List[Tuple[int, int]]]
AncMatT = List[List[int]]
PathFreqsT = List[Counter]


class Solution:
    def kth_ancestor(self, node: int, k: int, anc_mat: AncMatT) -> int:
        anc = node
        idx = 0
        while k:
            if k & 1:
                anc = anc_mat[anc][idx]
            idx += 1
            k >>= 1
        return anc

    def gen_anc_matrix(
        self,
        node: int,
        par: int,
        lvl: int,
        graph: GraphT,
        anc_mat: AncMatT,
        levels: List[int],
    ) -> None:
        levels[node] = lvl
        anc_mat[node].append(par)  # the 2^0 th ancestor of node is parent
        i = 1
        while (1 << i) <= lvl:
            anc = anc_mat[anc_mat[node][i - 1]][i - 1]
            anc_mat[node].append(anc)
            i += 1
        for child, _ in graph[node]:
            if child != par:
                self.gen_anc_matrix(child, node, lvl + 1, graph, anc_mat, levels)

    def get_lca(self, n1: int, n2: int, anc_mat: AncMatT, levels: List[int]) -> int:
        """
        Find the lowest common ancestor of the given two nodes
        """
        if levels[n1] > levels[n2]:
            n1, n2 = n2, n1
        n2 = self.kth_ancestor(n2, levels[n2] - levels[n1], anc_mat)
        if n1 == n2:
            return n1
        lvl = levels[n1]
        while lvl > 0:
            a1, a2 = self.kth_ancestor(n1, lvl, anc_mat), self.kth_ancestor(n2, lvl, anc_mat)
            if a1 == a2:
                lvl -= 1
            else:
                lvl = min(levels[a1], levels[a2]) - 1
                n1, n2 = a1, a2
        return anc_mat[n1][0]

    def gen_path_freq(
        self,
        node: int,
        par: int,
        graph: GraphT,
        weight_freqs: PathFreqsT,
        cur_freq: Counter,
    ) -> None:
        weight_freqs[node] = cur_freq.copy()
        for child, weight in graph[node]:
            if child != par:
                cur_freq[weight] += 1
                self.gen_path_freq(child, node, graph, weight_freqs, cur_freq)
                cur_freq[weight] -= 1

    def minOperationsQueries(
        self, n: int, edges: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        """
        Failed.

        Cannot solve this problem without going through the hints. Also, it
        is pretty much impossible to implement the LCA algorithm from scratch
        without any help.

        Basically, we DFS the tree from any node, and produce a weight frequency 
        for each node during DFS. Then we can obtain the weight frequency from
        the path between any two nodes by performing source weight frequency
        + destinatin weight frequency - 2 * lca weight frequency, where lca
        is the lowest common ancestor of source and destination. Then the
        answer to the source-destination pair is the total number of edges
        minus the most common count of weights.

        The most difficult part of this algorithm is undoubtedly the LCA. I
        need a lot of help to implement the LCA using binary lifting.
        """
        graph: GraphT = [[] for _ in range(n)]
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        # generate ancestor matrix
        anc_mat: AncMatT = [[] for _ in range(n)]
        levels = [0] * n
        self.gen_anc_matrix(0, 0, 0, graph, anc_mat, levels)

        # generate the frequency of the path to each node
        weight_freqs: PathFreqsT = [Counter() for _ in range(n)]
        self.gen_path_freq(0, 0, graph, weight_freqs, Counter())

        res = []
        for s, d in queries:
            lca = self.get_lca(s, d, anc_mat, levels)
            pf = weight_freqs[s] + weight_freqs[d] - weight_freqs[lca] - weight_freqs[lca]
            res.append(sum(pf.values()) - (pf.most_common(1)[0][1] if pf else 0))
        return res


44000