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

from collections import defaultdict
from math import log2, ceil
from typing import List

class Solution:
    def __init__(self):
        self.LOG = 0
        self.ancestors = []
        self.depth = []
        self.freq = []
        self.parent = []
        self.tree = defaultdict(list)
        self.n = 0

    def dfs(self, node, par, weight):
        self.parent[node] = par
        if par != -1:
            self.freq[node] = self.freq[par].copy()
            self.freq[node][weight] += 1
        
        for neighbor, w in self.tree[node]:
            if neighbor == par:
                continue
            self.depth[neighbor] = self.depth[node] + 1
            self.dfs(neighbor, node, w)

    def preprocessLCA(self, root):
        # Initialize LCA table for binary lifting
        self.LOG = ceil(log2(self.n))
        self.ancestors = [[-1] * (self.LOG + 1) for _ in range(self.n)]

        # First ancestor (2^0th = 1 step ancestor) is the parent
        for i in range(self.n):
            self.ancestors[i][0] = self.parent[i]

        # Binary lifting process: fill up ancestors table
        for j in range(1, self.LOG + 1):
            for i in range(self.n):
                if self.ancestors[i][j - 1] != -1:
                    self.ancestors[i][j] = self.ancestors[self.ancestors[i][j - 1]][j - 1]

    def lca(self, u, v):
        # Ensure u is the deeper node
        if self.depth[u] < self.depth[v]:
            u, v = v, u

        # Binary lift u up to the same depth as v
        diff = self.depth[u] - self.depth[v]
        for i in range(self.LOG + 1):
            if diff & (1 << i):
                u = self.ancestors[u][i]

        # If u and v are the same, u is the LCA
        if u == v:
            return u

        # Binary lift both u and v until their ancestors diverge
        for i in range(self.LOG, -1, -1):
            if self.ancestors[u][i] != self.ancestors[v][i]:
                u = self.ancestors[u][i]
                v = self.ancestors[v][i]

        # The parent of u (or v) is the LCA
        return self.parent[u]

    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        self.n = n
        self.freq = [defaultdict(int) for _ in range(n)]
        self.depth = [0] * n
        self.parent = [-1] * n

        # Build the tree
        for u, v, w in edges:
            self.tree[u].append((v, w))
            self.tree[v].append((u, w))

        # DFS to initialize frequency table and depth
        self.dfs(0, -1, 0)  # Assume node 0 is the root

        # Preprocess LCA
        self.preprocessLCA(0)

        res = []
        for a, b in queries:
            lca_ab = self.lca(a, b)
            freq_a = self.freq[a]
            freq_b = self.freq[b]
            freq_lca = self.freq[lca_ab]
            
            # Keys for the edge weights present in the path
            all_weights = set(freq_a.keys()).union(set(freq_b.keys()))

            if not all_weights:  # Handle the case where there are no edge weights in the path
                res.append(0)
                continue
            
            # Determine the number of changes required
            total_edges = sum(freq_a[w] + freq_b[w] - 2 * freq_lca[w] for w in all_weights)
            most_frequent_weight = max(freq_a[w] + freq_b[w] - 2 * freq_lca[w] for w in all_weights)
            
            # Minimum changes is total edges - most frequent edge count
            res.append(total_edges - most_frequent_weight)

        return res
38500