Tap here to switch tabs
Problem
Submissions

Problem: Find Weighted Median Node in Tree

Find Weighted Median Node in Tree asks you to process path queries on a weighted tree and return the first node where the distance from the path's start reaches at least half its total weight.

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≤2 \leq n ≤105\leq 10^5

  • edges.length == n - 1

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

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

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

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

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

  • 0≤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

Find Weighted Median Node in Tree asks you to process path queries on a weighted tree and return the first node where the distance from the path's start reaches at least half its total weight.

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≤2 \leq n ≤105\leq 10^5

  • edges.length == n - 1

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

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

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

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

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

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

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