DeepSeek LeetCode 3585. 树中找到带权中位节点 Java实现

问题描述给定一棵 n 个节点的无向带权树根节点为 0以及若干查询 queries[j] [u, v]。对于每个查询需要找到从 u 到 v 路径上的带权中位节点——即从 u 出发向 v 移动时第一个使得从 u 到该节点的边权之和 ≥ 路径总权值一半的节点。解题思路核心算法树上倍增LCA 二分跳跃1. 预处理以 0 为根 DFS计算每个节点的深度 depth[]、到根的距离 dist[]边权和以及倍增祖先表 parent[k][node]2^k 级祖先。2. 查询处理· 若 u v答案就是 u 本身。· 否则求 u 和 v 的 LCA计算路径总权值 total dist[u] dist[v] - 2*dist[lca]半阈值 half (total 1) / 2。· 情况一中位节点在 u → LCA 这段上dist[u] - dist[lca] half。从 u 出发向上跳找到最后一个满足 dist[u] - dist[ancestor] half 的祖先答案就是该祖先的父节点。· 情况二中位节点在 LCA → v 这段上。从 v 出发向上跳找到第一个满足 dist[ancestor] - dist[lca] remaining 的祖先remaining half - (dist[u] - dist[lca])。Java 实现javaimport java.util.*;class Solution {private Listint[][] adj;private int[] depth;private long[] dist;private int[][] parent;private int LOG;public int[] findMedian(int n, int[][] edges, int[][] queries) {// 1. 建图adj new List[n];for (int i 0; i n; i) adj[i] new ArrayList();for (int[] e : edges) {int u e[0], v e[1], w e[2];adj[u].add(new int[]{v, w});adj[v].add(new int[]{u, w});}// 2. 预处理深度、距离、倍增表LOG (int)(Math.log(n) / Math.log(2)) 1;depth new int[n];dist new long[n];parent new int[LOG][n];for (int[] row : parent) Arrays.fill(row, -1);dfs(0, -1, 0, 0L);for (int k 1; k LOG; k) {for (int i 0; i n; i) {if (parent[k-1][i] ! -1) {parent[k][i] parent[k-1][parent[k-1][i]];}}}// 3. 处理每个查询int[] ans new int[queries.length];for (int i 0; i queries.length; i) {ans[i] getWeightedMedian(queries[i][0], queries[i][1]);}return ans;}private void dfs(int u, int p, int d, long w) {depth[u] d;dist[u] w;parent[0][u] p;for (int[] e : adj[u]) {int v e[0], weight e[1];if (v p) continue;dfs(v, u, d 1, w weight);}}private int getKthAncestor(int u, int k) {for (int i 0; i LOG; i) {if (((k i) 1) 1) {u parent[i][u];if (u -1) break;}}return u;}private int getLCA(int u, int v) {if (depth[u] depth[v]) { int tmp u; u v; v tmp; }u getKthAncestor(u, depth[u] - depth[v]);if (u v) return u;for (int i LOG - 1; i 0; i--) {if (parent[i][u] ! parent[i][v]) {u parent[i][u];v parent[i][v];}}return parent[0][u];}private int getWeightedMedian(int u, int v) {if (u v) return u;int lca getLCA(u, v);long total dist[u] dist[v] - 2 * dist[lca];long half (total 1) / 2; // 向上取整// 情况1中位节点在 u - lca 这一段if (dist[u] - dist[lca] half) {int cur u;// 向上跳到最后一个 dist[u] - dist[ancestor] half 的节点for (int i LOG - 1; i 0; i--) {int nxt parent[i][cur];if (nxt ! -1 dist[u] - dist[nxt] half) {cur nxt;}}return parent[0][cur]; // 它的父节点就是答案}// 情况2中位节点在 lca - v 这一段else {long need half - (dist[u] - dist[lca]); // 从 lca 往下还需要走的权值int cur v;for (int i LOG - 1; i 0; i--) {int nxt parent[i][cur];if (nxt ! -1 depth[nxt] depth[lca] dist[nxt] - dist[lca] need) {cur nxt;}}return cur;}}}复杂度分析· 时间复杂度预处理 DFS 为 O(n)构建倍增表为 O(n log n)每个查询为 O(log n)总复杂度 O((n q) log n)。· 空间复杂度邻接表 O(n)倍增表 O(n log n)总复杂度 O(n log n)。关键点边权和路径总权值可能超过 32 位整数范围n 和 w 均可达 10^9务必使用 long 类型存储。