3585. Find Weighted Median Node in Tree Hard
1/**
2 * [3585] Find Weighted Median Node in Tree
3 *
4 * 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 vi with weight wi.
5 * 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.
6 * 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.
7 * Return an array ans, where ans[j] is the node index of the weighted median for queries[j].
8 *
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">n = 2, edges = [[0,1,7]], queries = [[1,0],[0,1]]</span>
12 * Output: <span class="example-io">[0,1]</span>
13 * Explanation:
14 * <img src="https://assets.leetcode.com/uploads/2025/05/26/screenshot-2025-05-26-at-193447.png" style="width: 200px; height: 64px;" />
15 * <table style="border: 1px solid black;">
16 * <thead>
17 * <tr>
18 * <th style="border: 1px solid black;">Query</th>
19 * <th style="border: 1px solid black;">Path</th>
20 * <th style="border: 1px solid black;">Edge<br />
21 * Weights</th>
22 * <th style="border: 1px solid black;">Total<br />
23 * Path<br />
24 * Weight</th>
25 * <th style="border: 1px solid black;">Half</th>
26 * <th style="border: 1px solid black;">Explanation</th>
27 * <th style="border: 1px solid black;">Answer</th>
28 * </tr>
29 * </thead>
30 * <tbody>
31 * <tr>
32 * <td style="border: 1px solid black;">[1, 0]</td>
33 * <td style="border: 1px solid black;">1 → 0</td>
34 * <td style="border: 1px solid black;">[7]</td>
35 * <td style="border: 1px solid black;">7</td>
36 * <td style="border: 1px solid black;">3.5</td>
37 * <td style="border: 1px solid black;">Sum from 1 → 0 = 7 >= 3.5, median is node 0.</td>
38 * <td style="border: 1px solid black;">0</td>
39 * </tr>
40 * <tr>
41 * <td style="border: 1px solid black;">[0, 1]</td>
42 * <td style="border: 1px solid black;">0 → 1</td>
43 * <td style="border: 1px solid black;">[7]</td>
44 * <td style="border: 1px solid black;">7</td>
45 * <td style="border: 1px solid black;">3.5</td>
46 * <td style="border: 1px solid black;">Sum from 0 → 1 = 7 >= 3.5, median is node 1.</td>
47 * <td style="border: 1px solid black;">1</td>
48 * </tr>
49 * </tbody>
50 * </table>
51 * </div>
52 * <strong class="example">Example 2:
53 * <div class="example-block">
54 * Input: <span class="example-io">n = 3, edges = [[0,1,2],[2,0,4]], queries = [[0,1],[2,0],[1,2]]</span>
55 * Output: <span class="example-io">[1,0,2]</span>
56 * Explanation:
57 * <img src="https://assets.leetcode.com/uploads/2025/05/26/screenshot-2025-05-26-at-193610.png" style="width: 180px; height: 149px;" />
58 * <table style="border: 1px solid black;">
59 * <thead>
60 * <tr>
61 * <th style="border: 1px solid black;">Query</th>
62 * <th style="border: 1px solid black;">Path</th>
63 * <th style="border: 1px solid black;">Edge<br />
64 * Weights</th>
65 * <th style="border: 1px solid black;">Total<br />
66 * Path<br />
67 * Weight</th>
68 * <th style="border: 1px solid black;">Half</th>
69 * <th style="border: 1px solid black;">Explanation</th>
70 * <th style="border: 1px solid black;">Answer</th>
71 * </tr>
72 * </thead>
73 * <tbody>
74 * <tr>
75 * <td style="border: 1px solid black;">[0, 1]</td>
76 * <td style="border: 1px solid black;">0 → 1</td>
77 * <td style="border: 1px solid black;">[2]</td>
78 * <td style="border: 1px solid black;">2</td>
79 * <td style="border: 1px solid black;">1</td>
80 * <td style="border: 1px solid black;">Sum from 0 → 1 = 2 >= 1, median is node 1.</td>
81 * <td style="border: 1px solid black;">1</td>
82 * </tr>
83 * <tr>
84 * <td style="border: 1px solid black;">[2, 0]</td>
85 * <td style="border: 1px solid black;">2 → 0</td>
86 * <td style="border: 1px solid black;">[4]</td>
87 * <td style="border: 1px solid black;">4</td>
88 * <td style="border: 1px solid black;">2</td>
89 * <td style="border: 1px solid black;">Sum from 2 → 0 = 4 >= 2, median is node 0.</td>
90 * <td style="border: 1px solid black;">0</td>
91 * </tr>
92 * <tr>
93 * <td style="border: 1px solid black;">[1, 2]</td>
94 * <td style="border: 1px solid black;">1 → 0 → 2</td>
95 * <td style="border: 1px solid black;">[2, 4]</td>
96 * <td style="border: 1px solid black;">6</td>
97 * <td style="border: 1px solid black;">3</td>
98 * <td style="border: 1px solid black;">Sum from 1 → 0 = 2 < 3.<br />
99 * Sum from 1 → 2 = 2 + 4 = 6 >= 3, median is node 2.</td>
100 * <td style="border: 1px solid black;">2</td>
101 * </tr>
102 * </tbody>
103 * </table>
104 * </div>
105 * <strong class="example">Example 3:
106 * <div class="example-block">
107 * Input: <span class="example-io">n = 5, edges = [[0,1,2],[0,2,5],[1,3,1],[2,4,3]], queries = [[3,4],[1,2]]</span>
108 * Output: <span class="example-io">[2,2]</span>
109 * Explanation:
110 * <img src="https://assets.leetcode.com/uploads/2025/05/26/screenshot-2025-05-26-at-193857.png" style="width: 150px; height: 229px;" />
111 * <table style="border: 1px solid black;">
112 * <thead>
113 * <tr>
114 * <th style="border: 1px solid black;">Query</th>
115 * <th style="border: 1px solid black;">Path</th>
116 * <th style="border: 1px solid black;">Edge<br />
117 * Weights</th>
118 * <th style="border: 1px solid black;">Total<br />
119 * Path<br />
120 * Weight</th>
121 * <th style="border: 1px solid black;">Half</th>
122 * <th style="border: 1px solid black;">Explanation</th>
123 * <th style="border: 1px solid black;">Answer</th>
124 * </tr>
125 * </thead>
126 * <tbody>
127 * <tr>
128 * <td style="border: 1px solid black;">[3, 4]</td>
129 * <td style="border: 1px solid black;">3 → 1 → 0 → 2 → 4</td>
130 * <td style="border: 1px solid black;">[1, 2, 5, 3]</td>
131 * <td style="border: 1px solid black;">11</td>
132 * <td style="border: 1px solid black;">5.5</td>
133 * <td style="border: 1px solid black;">Sum from 3 → 1 = 1 < 5.5.<br />
134 * Sum from 3 → 0 = 1 + 2 = 3 < 5.5.<br />
135 * Sum from 3 → 2 = 1 + 2 + 5 = 8 >= 5.5, median is node 2.</td>
136 * <td style="border: 1px solid black;">2</td>
137 * </tr>
138 * <tr>
139 * <td style="border: 1px solid black;">[1, 2]</td>
140 * <td style="border: 1px solid black;">1 → 0 → 2</td>
141 * <td style="border: 1px solid black;">[2, 5]</td>
142 * <td style="border: 1px solid black;">7</td>
143 * <td style="border: 1px solid black;">3.5</td>
144 * <td style="border: 1px solid black;">
145 * Sum from 1 → 0 = 2 < 3.5.<br />
146 * Sum from 1 → 2 = 2 + 5 = 7 >= 3.5, median is node 2.
147 * </td>
148 * <td style="border: 1px solid black;">2</td>
149 * </tr>
150 * </tbody>
151 * </table>
152 * </div>
153 *
154 * Constraints:
155 *
156 * 2 <= n <= 10^5
157 * edges.length == n - 1
158 * edges[i] == [ui, vi, wi]
159 * 0 <= ui, vi < n
160 * 1 <= wi <= 10^9
161 * 1 <= queries.length <= 10^5
162 * queries[j] == [uj, vj]
163 * 0 <= uj, vj < n
164 * The input is generated such that edges represents a valid tree.
165 *
166 */
167pub struct Solution {}
168
169// problem: https://leetcode.com/problems/find-weighted-median-node-in-tree/
170// discuss: https://leetcode.com/problems/find-weighted-median-node-in-tree/discuss/?currentPage=1&orderBy=most_votes&query=
171
172// submission codes start here
173
174impl Solution {
175 pub fn find_median(n: i32, edges: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
176 vec![]
177 }
178}
179
180// submission codes end
181
182#[cfg(test)]
183mod tests {
184 use super::*;
185
186 #[test]
187 fn test_3585() {
188 }
189}
190Back
© 2026 bowen.ge All Rights Reserved.