Minimum Edge Weight Equilibrium Queries in a Tree
There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with weight wi in the tree.
You are also given a 2D integer array queries of length m, where queries[i] = [ai, bi]. For each query, find the minimum number of operations required to make the weight of every edge on the path from ai to bi equal. In one operation, you can choose any edge of the tree and change its weight to any value.
Note that:
- Queries are independent of each other, meaning that the tree returns to its initial state on each new query.
- The path from
aitobiis a sequence of distinct nodes starting with nodeaiand ending with nodebisuch that every two adjacent nodes in the sequence share an edge in the tree.
Return an array answer of length m where answer[i] is the answer to the i^th query.
Example 1
Input
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]]Output
[0,0,1,3]For each query, the paths from 0 to 3 and from 3 to 6 already have equal edge weights, the path from 2 to 6 needs one edge changed to weight 2, and the path from 0 to 6 needs three edges changed to weight 2.
Example 2
Input
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]]Output
[1,2,2,3]For each query, changing the indicated minority-weight edges on the path to weight 6 gives the minimum operation counts 1, 2, 2, and 3 respectively.
Constraints
- 1 <= n <= 10^4
- edges.length == n - 1
- edges[i].length == 3
- 0 <= ui, vi < n
- 1 <= wi <= 26
- The input is generated such that
edgesrepresents a valid tree. - 1 <= queries.length == m <= 2 * 10^4
- queries[i].length == 2
- 0 <= ai, bi < n