Find Weighted Median Node in Tree
You are given an integer n and an undirected, weighted tree rooted at node 0 with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates an edge from node ui to node vi with weight wi.
The weighted median node is defined as the first node x on the path from ui to vi such that the sum of edge weights from ui to x is greater than or equal to half of the total path weight.
You are given a 2D integer array queries. For each queries[j] = [uj, vj], determine the weighted median node along the path from uj to vj.
Return an array ans, where ans[j] is the node index of the weighted median for queries[j].
Example 1
Input
n = 2, edges = [[0,1,7]], queries = [[1,0],[0,1]]Output
[0,1]For query
[1, 0], the path weight is 7 and node 0 is the first node whose accumulated distance from 1 reaches at least 3.5; for query [0, 1], node 1 is the first such node.Example 2
Input
n = 3, edges = [[0,1,2],[2,0,4]], queries = [[0,1],[2,0],[1,2]]Output
[1,0,2]The first two queries each traverse one edge, and for query
[1, 2] the accumulated path weight first reaches at least half of 6 at node 2.Constraints
- 2 <= n <= 10^5
- edges.length == n - 1
- edges[i] == [ui, vi, wi]
- 0 <= ui, vi < n
- 1 <= wi <= 10^9
- 1 <= queries.length <= 10^5
- queries[j] == [uj, vj]
- 0 <= uj, vj < n
- The input is generated such that edges represents a valid tree.