LeetCode Problem 3515

Difficulty: 🔴 Hard
Topics: Array, Tree, Depth-First Search, Binary Indexed Tree, Segment Tree

Solution

LeetCode 3515. Shortest Path in a Weighted Tree

Problem Understanding

We are given a weighted tree with n nodes, rooted at node 1.

A tree has exactly one simple path between any pair of nodes. Since the tree is rooted at node 1, every node has a unique path from the root.

The queries come in two forms:

• [1, u, v, w'] updates the weight of the existing edge (u, v) to a new value w'.
• [2, x] asks for the current shortest path distance from root node 1 to node x.

Because the graph is a tree, the phrase "shortest path" is actually simpler than it sounds. There is only one path from node 1 to node x, so the answer is simply the sum of edge weights along that path.

The challenge comes from the updates. After changing an edge weight, many root-to-node distances may change. Since both n and the number of queries can be as large as 100,000, recomputing distances after every update is far too expensive.

The input consists of:

• n, the number of nodes.
• edges, describing the weighted tree.
• queries, containing updates and distance requests.

The output should contain one answer for every query of type [2, x].

The constraints tell us several important things:

• Up to 100,000 nodes.
• Up to 100,000 queries.
• Edge updates happen online.
• We need approximately O(log n) per query, not O(n).

Important edge cases include:

• A tree with only two nodes.
• Queries asking for the root itself, whose distance is always 0.
• Multiple updates applied to the same edge.
• Deep chain-shaped trees where a naive subtree traversal becomes expensive.
• Large numbers of updates before any distance query.

Approaches

Brute Force

A straightforward solution is to maintain the tree and process queries directly.

For every update:

• Change the edge weight.

For every distance query:

• Run a DFS or BFS from the root.
• Recompute the distance to the requested node.

This is correct because the traversal computes the exact root-to-node distance using the current weights.

However, each query may require traversing the entire tree, costing O(n). With up to 100,000 queries, the total complexity becomes O(nq), which can reach 10^10 operations.

This is far too slow.

Key Insight

Consider an edge connecting a parent node p and child node c.

Suppose the edge weight changes by:

delta = newWeight - oldWeight

Which root-to-node distances change?

Only nodes whose path from the root passes through that edge.

In a rooted tree, that means exactly the nodes in the subtree rooted at c.

Therefore:

• Updating an edge corresponds to adding delta to every node in one subtree.
• Querying a node asks for its current root distance.

This transforms the problem into:

• Subtree range updates.
• Point queries.

Using an Euler Tour, every subtree becomes a contiguous interval.

Then a Fenwick Tree (Binary Indexed Tree) can support:

• Range add.
• Point query.

in O(log n) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nq)	O(n)	Recompute distances repeatedly
Optimal	O((n + q) log n)	O(n)	Euler Tour + Fenwick Tree range updates

Algorithm Walkthrough

1. Root the tree

Build the adjacency list and perform a DFS starting from node 1.

During DFS, determine:

• Parent of every node.
• Initial distance from root.
• Euler Tour entry time tin.
• Euler Tour exit time tout.

The Euler Tour is important because every subtree becomes a continuous interval.

2. Identify the child endpoint of every edge

For an update query (u, v):

• One endpoint is the parent.
• The other endpoint is the child.

The subtree affected by the update is always the child's subtree.

Store the current weight of each edge and remember which endpoint is the child.

3. Compute initial root distances

During DFS, maintain:

dist[node]

which is the root-to-node distance using the original weights.

These values never need to be recomputed.

4. Flatten the tree

Using Euler Tour timestamps:

subtree(node) = [tin[node], tout[node]]

Every node in the subtree occupies a contiguous segment.

This allows subtree updates to become interval updates.

5. Build a Fenwick Tree

The Fenwick Tree stores accumulated updates.

We use the standard range-update/point-query technique:

To add delta to interval [L, R]:

BIT[L] += delta
BIT[R+1] -= delta

The prefix sum at a position gives the total accumulated change.

6. Process update queries

For update:

[1, u, v, newWeight]

Find the child endpoint.

Compute:

delta = newWeight - oldWeight

All nodes in that child's subtree gain this amount.

Perform:

add(delta) on [tin[child], tout[child]]

Update the stored edge weight.

7. Process distance queries

For query:

[2, x]

The answer equals:

originalDistance[x]
+
all accumulated updates affecting x

The accumulated updates are obtained through a Fenwick Tree point query at tin[x].

Why it works

For every edge update, exactly the nodes in the child subtree have their root path modified. The Euler Tour maps that subtree to a contiguous interval. The Fenwick Tree efficiently accumulates all updates applied to intervals. Therefore, the value retrieved at a node's Euler position equals the sum of all edge-weight changes affecting that node. Adding this value to the original root distance produces the correct current distance.

Problem Understanding

This problem asks us to maintain and query shortest path distances in a weighted tree rooted at node 1. The input consists of n nodes connected by n - 1 undirected, weighted edges, forming a tree. Each query either updates the weight of an edge or asks for the shortest path distance from the root to a specific node. The expected output is an array of distances corresponding to the queries of type [2, x].

The input guarantees a valid tree, meaning there is exactly one path between any two nodes. The constraints are significant: n and the number of queries q can each go up to 10^5. This means a naive approach that recomputes the path distance from the root to x for every query would be too slow. Updates to edge weights must also propagate efficiently to affected paths.

Edge cases include trees with a single node, queries that repeatedly update the same edge, and queries that ask for the root's distance (which should always be zero).

Approaches

Brute-Force Approach

A straightforward solution is to store the tree in an adjacency list. For each type [2, x] query, perform a depth-first search (DFS) from the root to calculate the distance to node x. For type [1, u, v, w'] updates, simply modify the weight in the adjacency list.

This approach is correct because DFS always finds the unique path in a tree, but it is too slow. Each [2, x] query takes O(n) in the worst case, leading to an overall complexity of O(n * q), which can reach 10^10 operations.

Optimal Approach

The key insight is that the shortest path distance from the root to a node is the sum of edge weights along the unique path from the root. We can precompute the distance from the root to each node using DFS. For updates, instead of recalculating distances for all descendants, we can maintain a mapping of edges to their weight and propagate differences using a Binary Indexed Tree (Fenwick Tree) or Segment Tree over the DFS traversal order. This allows each query to be handled in O(log n) time.

The main steps involve:

1. Flatten the tree into an Euler tour or DFS order to represent subtree ranges.
2. Store distances from the root in an array.
3. Maintain edge weights and update subtree distances efficiently for [1, u, v, w'] queries using a tree-based range update.
4. Answer [2, x] queries in O(1) using the stored distance array combined with updates.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * q)	O(n)	DFS per query, too slow for n, q ~ 10^5
Optimal	O((n + q) log n)	O(n)	Precompute distances, update subtree efficiently with Segment Tree/BIT

Algorithm Walkthrough

1. Represent the tree as an adjacency list for quick access to neighbors and edge weights.

2. Perform a DFS from the root to compute dist[node], the distance from the root to each node, and record entry and exit times for subtree ranges.

3. Map each edge to the deeper node in the tree. This allows subtree updates when edge weights change.

4. Initialize a Segment Tree or Fenwick Tree to allow efficient range additions to propagate edge weight changes to all descendants.

5. For each query:

6. If it is [1, u, v, w'], compute the difference delta = w' - current_weight and apply a range update to the subtree rooted at the deeper node of (u, v) in the Segment Tree or BIT.

7. If it is [2, x], return dist[x] plus any accumulated update from the Segment Tree/BIT.

8. Collect and return the results for all [2, x] queries.

Why it works: By precomputing distances and using a tree flattening with range updates, we maintain an invariant where each node's distance is correct relative to the root. Subtree propagation ensures any weight change affects all relevant descendant paths without recomputing from scratch.

Python Solution

from typing import List
import sys

class Solution:
    def treeQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        sys.setrecursionlimit(300000)

        graph = [[] for _ in range(n + 1)]

        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        parent = [0] * (n + 1)
        dist = [0] * (n + 1)
        tin = [0] * (n + 1)
        tout = [0] * (n + 1)

        edge_weight = {}
        edge_child = {}

        timer = 0

        def dfs(node: int, par: int) -> None:
            nonlocal timer

            timer += 1
            tin[node] = timer

            for nxt, w in graph[node]:
                if nxt == par:
                    continue

                parent[nxt] = node
                dist[nxt] = dist[node] + w

                key = (min(node, nxt), max(node, nxt))
                edge_weight[key] = w
                edge_child[key] = nxt

                dfs(nxt, node)

            tout[node] = timer

        dfs(1, 0)

        class Fenwick:
            def __init__(self, size: int):
                self.n = size
                self.bit = [0] * (size + 2)

            def add(self, idx: int, delta: int) -> None:
                while idx <= self.n:
                    self.bit[idx] += delta
                    idx += idx & -idx

            def range_add(self, left: int, right: int, delta: int) -> None:
                self.add(left, delta)
                self.add(right + 1, -delta)

            def point_query(self, idx: int) -> int:
                res = 0
                while idx > 0:
                    res += self.bit[idx]
                    idx -= idx & -idx
                return res

        bit = Fenwick(n)

        answer = []

        for query in queries:
            if query[0] == 1:
                _, u, v, new_weight = query

                key = (min(u, v), max(u, v))

                old_weight = edge_weight[key]
                delta = new_weight - old_weight

                child = edge_child[key]

                bit.range_add(
                    tin[child],
                    tout[child],
                    delta
                )

                edge_weight[key] = new_weight

            else:
                _, x = query

                current_distance = (
                    dist[x]
                    + bit.point_query(tin[x])
                )

                answer.append(current_distance)

        return answer

Implementation Explanation

The DFS serves three purposes simultaneously.

First, it computes the original root distance for every node.

Second, it determines parent-child relationships, which lets us identify which endpoint of an updated edge represents the affected subtree.

Third, it generates Euler Tour timestamps. Every subtree becomes a continuous interval [tin, tout].

The Fenwick Tree is used in range-update/point-query mode. When an edge weight changes, we compute the difference between the new and old weight and add that difference across the child's entire subtree interval.

For a distance query, we start with the original root distance and add all accumulated subtree updates affecting that node. The Fenwick Tree prefix sum gives exactly that amount. from typing import List, Dict from collections import defaultdict

class Solution: def treeQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]: tree = defaultdict(list) edge_to_weight = {} for u, v, w in edges: tree[u].append(v) tree[v].append(u) edge_to_weight[frozenset({u, v})] = w

    dist = [0] * (n + 1)
    parent = [0] * (n + 1)
    in_time = [0] * (n + 1)
    out_time = [0] * (n + 1)
    timer = 0

    def dfs(node: int, par: int):
        nonlocal timer
        timer += 1
        in_time[node] = timer
        for nei in tree[node]:
            if nei != par:
                dist[nei] = dist[node] + edge_to_weight[frozenset({node, nei})]
                parent[nei] = node
                dfs(nei, node)
        out_time[node] = timer
    
    dfs(1, 0)
    
    # Fenwick Tree for range updates
    bit = [0] * (n + 2)
    
    def update(idx: int, val: int):
        while idx <= n:
            bit[idx] += val
            idx += idx & -idx
    
    def range_update(l: int, r: int, val: int):
        update(l, val)
        update(r + 1, -val)
    
    def query(idx: int) -> int:
        res = 0
        while idx > 0:
            res += bit[idx]
            idx -= idx & -idx
        return res

    answer = []
    for q in queries:
        if q[0] == 1:
            _, u, v, w_new = q
            edge = frozenset({u, v})
            w_old = edge_to_weight[edge]
            delta = w_new - w_old
            edge_to_weight[edge] = w_new
            deeper = u if parent[u] == v else v
            range_update(in_time[deeper], out_time[deeper], delta)
        else:
            _, x = q
            answer.append(dist[x] + query(in_time[x]))
    
    return answer

**Explanation:** We first build the tree and precompute distances using DFS. Each node gets an `in_time` and `out_time` to define its subtree. A Binary Indexed Tree efficiently propagates weight updates to subtrees. Queries for distances simply read `dist[x]` plus any accumulated subtree updates.

## Go Solution

```go
package main

func treeQueries(n int, edges [][]int, queries [][]int) []int {
	graph := make([][][2]int, n+1)

	for _, e := range edges {
		u, v, w := e[0], e[1], e[2]
		graph[u] = append(graph[u], [2]int{v, w})
		graph[v] = append(graph[v], [2]int{u, w})
	}

	parent := make([]int, n+1)
	dist := make([]int64, n+1)
	tin := make([]int, n+1)
	tout := make([]int, n+1)

	edgeWeight := make(map[[2]int]int)
	edgeChild := make(map[[2]int]int)

	timer := 0

	var dfs func(int, int)

	dfs = func(node int, par int) {
		timer++
		tin[node] = timer

		for _, edge := range graph[node] {
			next := edge[0]
			weight := edge[1]

			if next == par {
				continue
			}

			parent[next] = node
			dist[next] = dist[node] + int64(weight)

			key := [2]int{min(node, next), max(node, next)}

			edgeWeight[key] = weight
			edgeChild[key] = next

			dfs(next, node)
		}

		tout[node] = timer
	}

	dfs(1, 0)

	type Fenwick struct {
		n   int
		bit []int64
	}

	newFenwick := func(size int) *Fenwick {
		return &Fenwick{
			n:   size,
			bit: make([]int64, size+2),
		}
	}

	bit := newFenwick(n)

	add := func(idx int, delta int64) {
		for idx <= bit.n {
			bit.bit[idx] += delta
			idx += idx & -idx
		}
	}

	rangeAdd := func(left, right int, delta int64) {
		add(left, delta)
		add(right+1, -delta)
	}

	pointQuery := func(idx int) int64 {
		var res int64

		for idx > 0 {
			res += bit.bit[idx]
			idx -= idx & -idx
		}

		return res
	}

	ans := make([]int, 0)

	for _, q := range queries {
		if q[0] == 1 {
			u, v, newWeight := q[1], q[2], q[3]

			key := [2]int{min(u, v), max(u, v)}

			oldWeight := edgeWeight[key]
			delta := int64(newWeight - oldWeight)

			child := edgeChild[key]

			rangeAdd(
				tin[child],
				tout[child],
				delta,
			)

			edgeWeight[key] = newWeight
		} else {
			x := q[1]

			cur := dist[x] + pointQuery(tin[x])

			ans = append(ans, int(cur))
		}
	}

	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Go-Specific Notes

The Go implementation uses int64 for stored distances and Fenwick values. Although the final answer fits comfortably within typical constraints, using int64 avoids overflow concerns when many updates accumulate.

Maps with key type [2]int provide an efficient way to identify edges regardless of endpoint ordering.

Worked Examples

Example 1

Input:

n = 2
edges = [[1,2,7]]
queries = [[2,2],[1,1,2,4],[2,2]]

After DFS:

Node	dist	tin	tout
1	0	1	2
2	7	2	2

Processing queries:

Query	Fenwick Effect	Answer
[2,2]	none	7
[1,1,2,4]	add -3 to subtree(2)	-
[2,2]	node 2 gets -3	4

Output:

[7,4]

Example 2

Tree:

1
├─2 (2)
└─3 (4)

DFS values:

Node	dist	tin
1	0	1
2	2	2
3	4	3

Processing:

Query	Result
[2,1]	0
[2,3]	4
update (1,3): 4→7	delta = +3
[2,2]	2
[2,3]	7

Output:

[0,4,2,7]

Example 3

Tree:

1 --2--> 2 --1--> 3 --5--> 4

Original distances:

Node	Distance
1	0
2	2
3	3
4	8

Update:

(2,3): 1 -> 3
delta = +2

Affected subtree:

{3,4}

Updated distances:

Node	New Distance
1	0
2	2
3	5
4	10

Query results:

[8,3,2,5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + q) log n)	DFS preprocessing is O(n), each query is O(log n)
Space	O(n)	Graph, Euler arrays, maps, and Fenwick tree

The DFS visits every node and edge once. Every update becomes a single subtree range update in the Fenwick Tree, and every distance query becomes a single point query. Both operations require O(log n) time. Since there are at most q queries, the total complexity is O((n + q) log n).

Test Cases

sol = Solution()

# Example 1
assert sol.treeQueries(
    2,
    [[1, 2, 7]],
    [[2, 2], [1, 1, 2, 4], [2, 2]]
) == [7, 4]  # basic update

# Example 2
assert sol.treeQueries(
    3,
    [[1, 2, 2], [1, 3, 4]],
    [[2, 1], [2, 3], [1, 1, 3, 7], [2, 2], [2, 3]]
) == [0, 4, 2, 7]  # root query and update

# Example 3
assert sol.treeQueries(
    4,
    [[1, 2, 2], [2, 3, 1], [3, 4, 5]],
    [[2, 4], [2, 3], [1, 2, 3, 3], [2, 2], [2, 3]]
) == [8, 3, 2, 5]  # subtree update

# Single node tree
assert sol.treeQueries(
    1,
    [],
    [[2, 1], [2, 1]]
) == [0, 0]  # root only

# Multiple updates on same edge
assert sol.treeQueries(
    2,
    [[1, 2, 5]],
    [
        [1, 1, 2, 10],
        [2, 2],
        [1, 1, 2, 3],
        [2, 2]
    ]
) == [10, 3]  # repeated edge updates

# Star tree
assert sol.treeQueries(
    4,
    [[1, 2, 1], [1, 3, 2], [1, 4, 3]],
    [
        [1, 1, 3, 10],
        [2, 2],
        [2, 3],
        [2, 4]
    ]
) == [1, 10, 3]  # update affects one branch only

# Deep chain
assert sol.treeQueries(
    5,
    [[1,2,1],[2,3,1],[3,4,1],[4,5,1]],
    [
        [1,3,4,5],
        [2,5],
        [2,3]
    ]
) == [8, 2]  # subtree propagation

Test Summary

Test	Why
Example 1	Smallest non-trivial tree
Example 2	Root queries and branch update
Example 3	Internal edge update affecting descendants
Single node tree	Minimum possible n
Multiple updates on same edge	Verifies delta handling
Star tree	Update should affect only one subtree
Deep chain	Tests long descendant propagation

Edge Cases

Querying the Root Node

The root node has no incoming edge, so its distance from itself is always zero. A common bug is accidentally applying subtree updates to the root. In this solution, updates only affect the subtree of a child endpoint, so node 1 remains unaffected unless it belongs to that subtree, which is impossible.

Repeated Updates on the Same Edge

Many implementations incorrectly add the new weight directly instead of applying the difference between old and new weights. If an edge changes from 5 to 10 and later from 10 to 3, the second update must apply -7, not +3. The solution stores the current edge weight and always computes a delta.

Deep Chain Trees

A tree may degenerate into a path of length 100,000. Naively traversing the entire subtree during every update would lead to quadratic behavior. The Euler Tour converts every subtree into a contiguous interval, allowing updates to remain O(log n) regardless of tree shape.

Updates on Edges Adjacent to the Root

When an edge directly connected to the root changes, the entire child subtree is affected. The parent-child orientation discovered during DFS correctly identifies the child endpoint, and the range update is applied to that entire subtree interval.

Large Numbers of Updates

A node may be affected by many updates before being queried. Instead of modifying every node immediately, the Fenwick Tree accumulates all updates lazily. The point query automatically sums all relevant changes when the answer is requested. tree := make([][]int, n+1) edgeWeight := make(map[[2]int]int) for _, e := range edges { u, v, w := e[0], e[1], e[2] tree[u] = append(tree[u], v) tree[v] = append(tree[v], u) if u < v { edgeWeight[[2]int{u, v}] = w } else { edgeWeight[[2]int{v, u}] = w } }

dist := make([]int, n+1)
parent := make([]int, n+1)
inTime := make([]int, n+1)
outTime := make([]int, n+1)
timer := 0

var dfs func(int, int)
dfs = func(node, par int) {
    timer++
    inTime[node] = timer
    for _, nei := range tree[node] {
        if nei != par {
            key := [2]int{node, nei}
            if node > nei {
                key = [2]int{nei, node}
            }
            dist[nei] = dist[node] + edgeWeight[key]
            parent[nei] = node
            dfs(nei, node)
        }
    }
    outTime[node] = timer
}
dfs(1, 0)

bit := make([]int, n+2)

update := func(idx, val int) {
    for idx <= n {
        bit[idx] += val
        idx += idx & -idx
    }
}
rangeUpdate := func(l, r, val int) {
    update(l, val)
    update(r+1, -val)
}
query := func(idx int) int {
    res := 0
    for idx > 0 {
        res += bit[idx]
        idx -= idx & -idx
    }
    return res
}

var answer []int
for _, q := range queries {
    if q[0] == 1 {
        u, v, wNew := q[1], q[2], q[3]
        key := [2]int{u, v}
        if u > v {
            key = [2]int{v, u}
        }
        wOld := edgeWeight[key]
        delta := wNew - wOld
        edgeWeight[key] = wNew
        deeper := u
        if parent[u] == v {
            deeper = u
        } else {
            deeper = v
        }
        rangeUpdate(inTime[de