3515. Shortest Path in a Weighted Tree LeetCode Solution

Last updated: April 21, 2025

In this guide, you will get 3515. Shortest Path in a Weighted Tree LeetCode Solution with the best time and space complexity. The solution to Shortest Path in a Weighted Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Shortest Path in a Weighted Tree solution in C++
Shortest Path in a Weighted Tree solution in Java
Shortest Path in a Weighted Tree solution in Python
Additional Resources

3515. Shortest Path in a Weighted Tree LeetCode Solution image

Problem Statement of Shortest Path in a Weighted Tree

You are given an integer n and an undirected, weighted tree rooted at node 1 with n nodes numbered from 1 to n. This is represented by a 2D array edges of length n – 1, where edges[i] = [ui, vi, wi] indicates an undirected edge from node ui to vi with weight wi.
You are also given a 2D integer array queries of length q, where each queries[i] is either:

[1, u, v, w’] – Update the weight of the edge between nodes u and v to w’, where (u, v) is guaranteed to be an edge present in edges.
[2, x] – Compute the shortest path distance from the root node 1 to node x.

Return an integer array answer, where answer[i] is the shortest path distance from node 1 to x for the ith query of [2, x].

Example 1:

Input: n = 2, edges = [[1,2,7]], queries = [[2,2],[1,1,2,4],[2,2]]
Output: [7,4]
Explanation:

Query [2,2]: The shortest path from root node 1 to node 2 is 7.
Query [1,1,2,4]: The weight of edge (1,2) changes from 7 to 4.
Query [2,2]: The shortest path from root node 1 to node 2 is 4.

Example 2:

Input: n = 3, edges = [[1,2,2],[1,3,4]], queries = [[2,1],[2,3],[1,1,3,7],[2,2],[2,3]]
Output: [0,4,2,7]
Explanation:

Query [2,1]: The shortest path from root node 1 to node 1 is 0.
Query [2,3]: The shortest path from root node 1 to node 3 is 4.
Query [1,1,3,7]: The weight of edge (1,3) changes from 4 to 7.
Query [2,2]: The shortest path from root node 1 to node 2 is 2.
Query [2,3]: The shortest path from root node 1 to node 3 is 7.

Example 3:

Input: n = 4, edges = [[1,2,2],[2,3,1],[3,4,5]], queries = [[2,4],[2,3],[1,2,3,3],[2,2],[2,3]]
Output: [8,3,2,5]
Explanation:

Query [2,4]: The shortest path from root node 1 to node 4 consists of edges (1,2), (2,3), and (3,4) with weights 2 + 1 + 5 = 8.
Query [2,3]: The shortest path from root node 1 to node 3 consists of edges (1,2) and (2,3) with weights 2 + 1 = 3.
Query [1,2,3,3]: The weight of edge (2,3) changes from 1 to 3.
Query [2,2]: The shortest path from root node 1 to node 2 is 2.
Query [2,3]: The shortest path from root node 1 to node 3 consists of edges (1,2) and (2,3) with updated weights 2 + 3 = 5.

Constraints:

1 <= n <= 105
edges.length == n – 1
edges[i] == [ui, vi, wi]
1 <= ui, vi <= n
1 <= wi <= 104
The input is generated such that edges represents a valid tree.
1 <= queries.length == q <= 105
queries[i].length == 2 or 4

queries[i] == [1, u, v, w'] or,
queries[i] == [2, x]
1 <= u, v, x <= n
(u, v) is always an edge from edges.
1 <= w' <= 104

Complexity Analysis

Time Complexity: O(n + q\log n)
Space Complexity: O(n + q)

3515. Shortest Path in a Weighted Tree LeetCode Solution in C++

class LazySegmentTree {
 public:
  explicit LazySegmentTree(int n) : n(n), tree(4 * n), lazy(4 * n) {}

  // Updates the range [l, r] by adding val.
  void addRange(int l, int r, int val) {
    addRange(0, 0, n - 1, l, r, val);
  }

  // Returns the value at index i.
  int query(int i) {
    return query(0, 0, n - 1, i);
  }

 private:
  const int n;       // the size of the input array
  vector<int> tree;  // the segment tree
  vector<int> lazy;  // the lazy propagation array

  void push(int treeIndex, int lo, int hi) {
    if (lazy[treeIndex] == 0)
      return;
    tree[treeIndex] += lazy[treeIndex];
    if (lo != hi) {
      lazy[2 * treeIndex + 1] += lazy[treeIndex];
      lazy[2 * treeIndex + 2] += lazy[treeIndex];
    }
    lazy[treeIndex] = 0;
  }

  void addRange(int treeIndex, int lo, int hi, int l, int r, int val) {
    push(treeIndex, lo, hi);
    if (r < lo || l > hi)  // [lo, hi] lies completely outside [l, r].
      return;
    if (l <= lo && hi <= r) {  // [lo, hi] lies completely inside [l, r].
      lazy[treeIndex] += val;
      push(treeIndex, lo, hi);
      return;
    }
    const int mid = (lo + hi) / 2;
    addRange(2 * treeIndex + 1, lo, mid, l, r, val);
    addRange(2 * treeIndex + 2, mid + 1, hi, l, r, val);
  }

  int query(int treeIndex, int lo, int hi, int i) {
    push(treeIndex, lo, hi);
    if (lo == hi)
      return tree[treeIndex];
    const int mid = (lo + hi) / 2;
    if (i <= mid)
      return query(2 * treeIndex + 1, lo, mid, i);
    return query(2 * treeIndex + 2, mid + 1, hi, i);
  }
};

class Solution {
 public:
  vector<int> treeQueries(int n, vector<vector<int>>& edges,
                          vector<vector<int>>& queries) {
    LazySegmentTree tree(n);
    vector<int> ans;
    vector<vector<pair<int, int>>> graph(n + 1);
    map<pair<int, int>, int> edgeWeights;

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      const int w = edge[2];
      graph[u].emplace_back(v, w);
      graph[v].emplace_back(u, w);
      edgeWeights[{min(u, v), max(u, v)}] = w;
    }

    // DFS: Euler tour and parent/distance tracking
    vector<int> inTime(n + 1);
    vector<int> outTime(n + 1);
    vector<int> dist(n + 1);
    vector<int> parent(n + 1);
    int time = 0;

    dfs(graph, 1, /*prev=*/-1, time, inTime, outTime, dist, parent);

    for (int i = 1; i <= n; ++i)
      tree.addRange(inTime[i], inTime[i], dist[i]);

    for (const vector<int>& query : queries) {
      const int type = query[0];
      if (type == 1) {
        const int u = query[1];
        const int v = query[2];
        const int newWeight = query[3];
        const auto key = pair<int, int>{min(u, v), max(u, v)};
        const int oldWeight = edgeWeights[key];
        const int delta = newWeight - oldWeight;
        edgeWeights[key] = newWeight;
        // Find child node (the one that's not the parent)
        const int child = (parent[v] == u) ? v : u;
        tree.addRange(inTime[child], outTime[child], delta);
      } else {
        const int x = query[1];
        ans.push_back(tree.query(inTime[x]));
      }
    }

    return ans;
  }

 private:
  void dfs(const vector<vector<pair<int, int>>>& graph, int u, int prev,
           int& time, vector<int>& inTime, vector<int>& outTime,
           vector<int>& dist, vector<int>& parent) {
    inTime[u] = time++;
    for (const auto& [v, w] : graph[u]) {
      if (v == prev)
        continue;
      dist[v] = dist[u] + w;
      parent[v] = u;
      dfs(graph, v, u, time, inTime, outTime, dist, parent);
    }
    outTime[u] = time - 1;
  }
};
/* code provided by PROGIEZ */

3515. Shortest Path in a Weighted Tree LeetCode Solution in Java

N/A
// code provided by PROGIEZ

3515. Shortest Path in a Weighted Tree LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents