Minimum weighted subgraph with the required paths ii

Array Dynamic Programming Bit Manipulation Tree Depth-First Search

49.7% acceptance

Feb 25, 2026

You are given an undirected weighted tree with n nodes, numbered from 0 to n - 1. It is represented by a 2D integer array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with weight wi. Additionally, you are given a 2D integer array queries, where queries[j] = [src1j, src2j, destj]. Return an array answer of length equal to queries.length, where answer[j] is the minimum total weight of a subtree such that it is possible to reach destj from both src1j and src2j using edges in this subtree. A subtree here is any connected subset of nodes and edges of the original tree forming a valid tree.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_weight(edges: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    // The minimum subtree connecting src1, src2, dest is the union of paths:
    // path(src1, dest) + path(src2, dest) - path(lca(src1,src2), dest) if lca is on path to dest
    // But cleaner: answer = (dist(src1,dest) + dist(src2,dest) + dist(src1,src2)) / 2
    // This is because the minimal Steiner tree in a tree is the union of the three paths,
    // and the total weight = (dist(a,b) + dist(b,c) + dist(a,c)) / 2
    // where meeting point m = lca(src1,src2,dest) varies, but:
    // weight = dist(src1,m) + dist(src2,m) + dist(dest,m)
    // = (dist(src1,src2) + dist(src1,dest) + dist(src2,dest)) / 2
    
    let n = edges.len() + 1;
    let mut adj: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
    for e in &edges {
      let (u, v, w) = (e[0] as usize, e[1] as usize, e[2] as i64);
      adj[u].push((v, w));
      adj[v].push((u, w));
    }
    
    // Binary lifting LCA with weighted distances
    let log = 17;
    let mut parent = vec![vec![0usize; log]; n];
    let mut pdist = vec![vec![0i64; log]; n]; // dist to 2^k-th ancestor
    let mut depth = vec![0i32; n];
    let mut dist_root = vec![0i64; n]; // weighted distance from root
    
    // BFS from root 0
    let mut order = Vec::with_capacity(n);
    let mut visited = vec![false; n];
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(0usize);
    parent[0][0] = 0;
    pdist[0][0] = 0;
    visited[0] = true;
    while let Some(u) = queue.pop_front() {
      order.push(u);
      for &(v, w) in &adj[u] {
        if !visited[v] {
          visited[v] = true;
          parent[v][0] = u;
          pdist[v][0] = w;
          depth[v] = depth[u] + 1;
          dist_root[v] = dist_root[u] + w;
          queue.push_back(v);
        }
      }
    }
    
    // Fill binary lifting table
    for k in 1..log {
      for &u in &order {
        let p = parent[u][k-1];
        parent[u][k] = parent[p][k-1];
        pdist[u][k] = pdist[u][k-1] + pdist[p][k-1];
      }
    }
    
    let lca = |mut u: usize, mut v: usize| -> usize {
      if depth[u] < depth[v] { std::mem::swap(&mut u, &mut v); }
      let diff = (depth[u] - depth[v]) as usize;
      for k in 0..log {
        if (diff >> k) & 1 == 1 {
          u = parent[u][k];
        }
      }
      if u == v { return u; }
      for k in (0..log).rev() {
        if parent[u][k] != parent[v][k] {
          u = parent[u][k];
          v = parent[v][k];
        }
      }
      parent[u][0]
    };
    
    let dist = |u: usize, v: usize| -> i64 {
      let l = lca(u, v);
      dist_root[u] + dist_root[v] - 2 * dist_root[l]
    };
    
    queries.iter().map(|q| {
      let (src1, src2, dest) = (q[0] as usize, q[1] as usize, q[2] as usize);
      let d = dist(src1, src2) + dist(src1, dest) + dist(src2, dest);
      (d / 2) as i32
    }).collect()
  }
}