#3585

Find Weighted Median Node in Tree

international master · 2080 · lc hard +32 · 26.2% accepted · 71 likes · top 4%

Description

A weighted undirected tree with n nodes (0-indexed, rooted at 0) is described by edges [ui, vi, wi].

For a path between two nodes, the weighted median node is the first node x (starting from the source) where the cumulative edge-weight from the source to x is at least half the total path weight.

Given queries [uj, vj], return an array ans where ans[j] is the weighted median node for the path from uj to vj.

Code

1

2

3

class Solution:
    def findMedian(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:

class Solution:
    def findMedian(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]: