Tap here to switch tabs
Problem
Submissions

Problem: Find Weighted Median Node in Tree

Try to solve the Find Weighted Median Node in Tree problem.

Statement

You are given an undirected weighted tree with n nodes labeled from $0$ to n −1- 1, and an array edges where edges[i] == [u_i, v_i, w_i] represents an edge between nodes u_i and v_i with weight w_i.

You are also given an array queries where queries[j] == [u_j, v_j].

For each query [u_j, v_j], consider the unique simple path starting from u_j and ending at v_j. Let the sum of all edge weights along this path be WW. The weighted median node is the first node xx encountered when traversing the path from u_j to v_j such that the sum of edge weights from u_j to xx is at least W2\frac{W}{2}.

Return an array of integers containing the answer for each query.

Constraints:

  • $2 \leq$ n ≤105\leq 10^5

  • edges.length ==== n −1- 1

  • edges[i] ==== [u_i, v_i, w_i]

  • $0 \leq$ u_i, v_i << n

  • $1 \leq$ w_i ≤109\leq 10^9

  • $1 \leq$ queries.length ≤105\leq 10^5

  • queries[j] ==== [u_j, v_j]

  • $0 \leq$ u_j, v_j << n

  • The input is generated such that edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Find Weighted Median Node in Tree

Try to solve the Find Weighted Median Node in Tree problem.

Statement

You are given an undirected weighted tree with n nodes labeled from $0$ to n −1- 1, and an array edges where edges[i] == [u_i, v_i, w_i] represents an edge between nodes u_i and v_i with weight w_i.

You are also given an array queries where queries[j] == [u_j, v_j].

For each query [u_j, v_j], consider the unique simple path starting from u_j and ending at v_j. Let the sum of all edge weights along this path be WW. The weighted median node is the first node xx encountered when traversing the path from u_j to v_j such that the sum of edge weights from u_j to xx is at least W2\frac{W}{2}.

Return an array of integers containing the answer for each query.

Constraints:

  • $2 \leq$ n ≤105\leq 10^5

  • edges.length ==== n −1- 1

  • edges[i] ==== [u_i, v_i, w_i]

  • $0 \leq$ u_i, v_i << n

  • $1 \leq$ w_i ≤109\leq 10^9

  • $1 \leq$ queries.length ≤105\leq 10^5

  • queries[j] ==== [u_j, v_j]

  • $0 \leq$ u_j, v_j << n

  • The input is generated such that edges represents a valid tree.