Kimi LeetCode 3553. 包含要求路径的最小带权子图 II Java实现

LeetCode 3553. 包含要求路径的最小带权子图 II核心思路这道题的关键数学观察是树上包含三个点的最小连通子树的边权和 (三点两两距离之和) / 2。在树结构中任意两点的路径唯一连接三个点的最小子树就是这三条路径的并集。通过 LCA最近公共祖先可以在 O(\log n) 时间内求出任意两点距离从而快速回答每个查询。算法步骤1. 建图将无向带权树用邻接表存储2. DFS 预处理以节点 0 为根记录每个节点的深度 depth[]、到根距离 dist[]、以及直接父节点 jump[][0]3. 倍增预处理jump[i][j] 表示节点 i 的 2^j 级祖先用于 O(\log n) 求 LCA4. 回答查询对每个 query [src1, src2, dest]计算answer (dist(src1,src2) dist(src1,dest) dist(src2,dest)) / 2复杂度- 时间O(n \log n q \log n)- 空间O(n \log n)---Java 实现javaclass Solution {public int[] minimumWeight(int[][] edges, int[][] queries) {int n edges.length 1;// 计算需要的倍增层数: 2^LOG nint LOG 0;while ((1 LOG) n) LOG;// 建图: graph[u] list of {v, weight}Listint[][] graph new ArrayList[n];for (int i 0; i n; i) {graph[i] new ArrayList();}for (int[] e : edges) {int u e[0], v e[1], w e[2];graph[u].add(new int[]{v, w});graph[v].add(new int[]{u, w});}// jump[i][j] 节点 i 的 2^j 级祖先int[][] jump new int[n][LOG];int[] depth new int[n];long[] dist new long[n]; // 节点到根的距离// 第一次 DFS 预处理深度、距离、父节点dfs(graph, 0, -1, jump, depth, dist);// 倍增预处理祖先表for (int j 1; j LOG; j) {for (int i 0; i n; i) {jump[i][j] jump[jump[i][j - 1]][j - 1];}}int[] ans new int[queries.length];for (int i 0; i queries.length; i) {int a queries[i][0];int b queries[i][1];int c queries[i][2];long d1 distance(a, b, jump, depth, dist);long d2 distance(a, c, jump, depth, dist);long d3 distance(b, c, jump, depth, dist);ans[i] (int) ((d1 d2 d3) / 2);}return ans;}// DFS 预处理: 深度、到根距离、直接父节点private void dfs(Listint[][] graph, int u, int parent,int[][] jump, int[] depth, long[] dist) {for (int[] e : graph[u]) {int v e[0], w e[1];if (v parent) continue;jump[v][0] u;depth[v] depth[u] 1;dist[v] dist[u] w;dfs(graph, v, u, jump, depth, dist);}}// 求 u 和 v 的最近公共祖先 LCAprivate int lca(int u, int v, int[][] jump, int[] depth) {if (depth[u] depth[v]) {int tmp u; u v; v tmp;}// 将 v 提升到与 u 同一深度int diff depth[v] - depth[u];for (int j 0; j jump[0].length; j) {if ((diff j 1) 1) {v jump[v][j];}}if (u v) return u;// 同时向上跳找到 LCA 的下一层for (int j jump[0].length - 1; j 0; j--) {if (jump[u][j] ! jump[v][j]) {u jump[u][j];v jump[v][j];}}return jump[u][0];}// 求 u 和 v 之间的带权距离private long distance(int u, int v, int[][] jump, int[] depth, long[] dist) {int w lca(u, v, jump, depth);return dist[u] dist[v] - 2 * dist[w];}}关键点说明要点 说明为什么答案 三边距离和 / 2 树上三个点的最小连通子树中每条边被覆盖的次数恰好是 2 次除了中心交汇点所以总边权 两两距离之和 / 2倍增层数 LOG 动态计算 2^LOG n对于 n \le 10^5 约需 1718 层long 类型 中间距离和可能超过 int 范围虽然最终答案在 int 内故 dist[] 和中间计算用 long根节点选择 任选节点作为根这里选 0树上距离与根的选择无关