Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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:
[2,2]: The shortest path from root node 1 to node 2 is 7.[1,1,2,4]: The weight of edge (1,2) changes from 7 to 4.[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:
[2,1]: The shortest path from root node 1 to node 1 is 0.[2,3]: The shortest path from root node 1 to node 3 is 4.[1,1,3,7]: The weight of edge (1,3) changes from 4 to 7.[2,2]: The shortest path from root node 1 to node 2 is 2.[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:
[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.[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.[1,2,3,3]: The weight of edge (2,3) changes from 1 to 3.[2,2]: The shortest path from root node 1 to node 2 is 2.[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 <= 105edges.length == n - 1edges[i] == [ui, vi, wi]1 <= ui, vi <= n1 <= wi <= 104edges represents a valid tree.1 <= queries.length == q <= 105queries[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' <= 104Problem summary: 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].
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Tree · Segment Tree
2 [[1,2,7]] [[2,2],[1,1,2,4],[2,2]]
3 [[1,2,2],[1,3,4]] [[2,1],[2,3],[1,1,3,7],[2,2],[2,3]]
4 [[1,2,2],[2,3,1],[3,4,5]] [[2,4],[2,3],[1,2,3,3],[2,2],[2,3]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3515: Shortest Path in a Weighted Tree
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3515: Shortest Path in a Weighted Tree
// package main
//
// // https://space.bilibili.com/206214
// type fenwick []int
//
// func newFenwickTree(n int) fenwick {
// return make(fenwick, n+1)
// }
//
// // 把下标 i 的元素增加 val
// func (f fenwick) update(i, val int) {
// for ; i < len(f); i += i & -i {
// f[i] += val
// }
// }
//
// // [1,i] 的元素和
// func (f fenwick) pre(i int) (s int) {
// for ; i > 0; i &= i - 1 {
// s += f[i]
// }
// return
// }
//
// func treeQueries(n int, edges [][]int, queries [][]int) (ans []int) {
// g := make([][]int, n+1)
// for _, e := range edges {
// x, y := e[0], e[1]
// g[x] = append(g[x], y)
// g[y] = append(g[y], x)
// }
//
// in := make([]int, n+1)
// out := make([]int, n+1)
// clock := 0
// var dfs func(int, int)
// dfs = func(x, fa int) {
// clock++
// in[x] = clock // 进来的时间
// for _, y := range g[x] {
// if y != fa {
// dfs(y, x)
// }
// }
// out[x] = clock // 离开的时间
// }
// dfs(1, 0)
//
// // 对于一条边 x-y（y 是 x 的儿子），把边权保存在 weight[y] 中
// weight := make([]int, n+1)
// diff := newFenwickTree(n)
// update := func(x, y, w int) {
// // 保证 y 是 x 的儿子
// if in[x] > in[y] {
// y = x
// }
// d := w - weight[y] // 边权的增量
// weight[y] = w
// // 把子树 y 中的最短路长度都增加 d（用差分树状数组维护）
// diff.update(in[y], d)
// diff.update(out[y]+1, -d)
// }
//
// for _, e := range edges {
// update(e[0], e[1], e[2])
// }
// for _, q := range queries {
// if q[0] == 1 {
// update(q[1], q[2], q[3])
// } else {
// ans = append(ans, diff.pre(in[q[1]]))
// }
// }
// return
// }
// Accepted solution for LeetCode #3515: Shortest Path in a Weighted Tree
package main
// https://space.bilibili.com/206214
type fenwick []int
func newFenwickTree(n int) fenwick {
return make(fenwick, n+1)
}
// 把下标 i 的元素增加 val
func (f fenwick) update(i, val int) {
for ; i < len(f); i += i & -i {
f[i] += val
}
}
// [1,i] 的元素和
func (f fenwick) pre(i int) (s int) {
for ; i > 0; i &= i - 1 {
s += f[i]
}
return
}
func treeQueries(n int, edges [][]int, queries [][]int) (ans []int) {
g := make([][]int, n+1)
for _, e := range edges {
x, y := e[0], e[1]
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
in := make([]int, n+1)
out := make([]int, n+1)
clock := 0
var dfs func(int, int)
dfs = func(x, fa int) {
clock++
in[x] = clock // 进来的时间
for _, y := range g[x] {
if y != fa {
dfs(y, x)
}
}
out[x] = clock // 离开的时间
}
dfs(1, 0)
// 对于一条边 x-y（y 是 x 的儿子），把边权保存在 weight[y] 中
weight := make([]int, n+1)
diff := newFenwickTree(n)
update := func(x, y, w int) {
// 保证 y 是 x 的儿子
if in[x] > in[y] {
y = x
}
d := w - weight[y] // 边权的增量
weight[y] = w
// 把子树 y 中的最短路长度都增加 d（用差分树状数组维护）
diff.update(in[y], d)
diff.update(out[y]+1, -d)
}
for _, e := range edges {
update(e[0], e[1], e[2])
}
for _, q := range queries {
if q[0] == 1 {
update(q[1], q[2], q[3])
} else {
ans = append(ans, diff.pre(in[q[1]]))
}
}
return
}
# Accepted solution for LeetCode #3515: Shortest Path in a Weighted Tree
#
# @lc app=leetcode id=3515 lang=python3
#
# [3515] Shortest Path in a Weighted Tree
#
# @lc code=start
class Solution:
def treeQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
adj = [[] for _ in range(n + 1)]
# Use a map to store edge weights to handle updates easily
# Key: tuple(sorted((u, v))), Value: weight
edge_weights = {}
for u, v, w in edges:
adj[u].append(v)
adj[v].append(u)
if u < v:
edge_weights[(u, v)] = w
else:
edge_weights[(v, u)] = w
# DFS to linearize the tree (Euler Tour / DFS order)
# and compute initial distances and subtree ranges
tin = [0] * (n + 1)
tout = [0] * (n + 1)
initial_dist = [0] * (n + 1)
# To identify which node is the child in an edge for updates
# parent[x] is not strictly needed if we check depth, but depth is useful.
# Let's verify parent/child relationship using depth or entry time.
# tin[child] > tin[parent] and tout[child] < tout[parent].
timer = 0
stack = [(1, 0, 0)] # node, parent, current_dist
# Iterative DFS to avoid recursion limit issues
# We need to process node on entry and on exit.
# To do this iteratively, we can push to stack or use a specific order.
# A simple way for tin/tout is to store the order.
# Let's stick to recursive for clarity, usually fine for 10^5 in Python if limit raised
import sys
sys.setrecursionlimit(200000)
def dfs(u, p, d):
nonlocal timer
timer += 1
tin[u] = timer
initial_dist[u] = d
for v in adj[u]:
if v != p:
# Weight of edge u-v
w = edge_weights[(min(u, v), max(u, v))]
dfs(v, u, d + w)
tout[u] = timer
dfs(1, 0, 0)
# Binary Indexed Tree for Range Update, Point Query
# We update range [l, r] with val, query point i
# Standard BIT: update(i, val) adds to i..n, query(i) sums 1..i
# Range update [l, r] with v:
# update(l, v)
# update(r + 1, -v)
# Point query at i:
# query(i) returns the accumulated value
bit = [0] * (n + 2)
def bit_update(idx, val):
while idx <= n:
bit[idx] += val
idx += idx & (-idx)
def bit_query(idx):
s = 0
while idx > 0:
s += bit[idx]
idx -= idx & (-idx)
return s
ans = []
for q in queries:
type = q[0]
if type == 1:
u, v, w_new = q[1], q[2], q[3]
# Determine which is child
# The child is the one with the larger tin because it was visited later in the descent
# Actually, in a tree edge (u, v), the child's interval is strictly inside the parent's interval (except for the root logic).
# The one with the larger tin is the child.
if tin[u] > tin[v]:
child = u
else:
child = v
key = (min(u, v), max(u, v))
old_w = edge_weights[key]
diff = w_new - old_w
edge_weights[key] = w_new
# Update range [tin[child], tout[child]]
bit_update(tin[child], diff)
bit_update(tout[child] + 1, -diff)
else:
x = q[1]
current_d = initial_dist[x] + bit_query(tin[x])
ans.append(current_d)
return ans
# @lc code=end
// Accepted solution for LeetCode #3515: Shortest Path in a Weighted Tree
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3515: Shortest Path in a Weighted Tree
// package main
//
// // https://space.bilibili.com/206214
// type fenwick []int
//
// func newFenwickTree(n int) fenwick {
// return make(fenwick, n+1)
// }
//
// // 把下标 i 的元素增加 val
// func (f fenwick) update(i, val int) {
// for ; i < len(f); i += i & -i {
// f[i] += val
// }
// }
//
// // [1,i] 的元素和
// func (f fenwick) pre(i int) (s int) {
// for ; i > 0; i &= i - 1 {
// s += f[i]
// }
// return
// }
//
// func treeQueries(n int, edges [][]int, queries [][]int) (ans []int) {
// g := make([][]int, n+1)
// for _, e := range edges {
// x, y := e[0], e[1]
// g[x] = append(g[x], y)
// g[y] = append(g[y], x)
// }
//
// in := make([]int, n+1)
// out := make([]int, n+1)
// clock := 0
// var dfs func(int, int)
// dfs = func(x, fa int) {
// clock++
// in[x] = clock // 进来的时间
// for _, y := range g[x] {
// if y != fa {
// dfs(y, x)
// }
// }
// out[x] = clock // 离开的时间
// }
// dfs(1, 0)
//
// // 对于一条边 x-y（y 是 x 的儿子），把边权保存在 weight[y] 中
// weight := make([]int, n+1)
// diff := newFenwickTree(n)
// update := func(x, y, w int) {
// // 保证 y 是 x 的儿子
// if in[x] > in[y] {
// y = x
// }
// d := w - weight[y] // 边权的增量
// weight[y] = w
// // 把子树 y 中的最短路长度都增加 d（用差分树状数组维护）
// diff.update(in[y], d)
// diff.update(out[y]+1, -d)
// }
//
// for _, e := range edges {
// update(e[0], e[1], e[2])
// }
// for _, q := range queries {
// if q[0] == 1 {
// update(q[1], q[2], q[3])
// } else {
// ans = append(ans, diff.pre(in[q[1]]))
// }
// }
// return
// }
// Accepted solution for LeetCode #3515: Shortest Path in a Weighted Tree
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3515: Shortest Path in a Weighted Tree
// package main
//
// // https://space.bilibili.com/206214
// type fenwick []int
//
// func newFenwickTree(n int) fenwick {
// return make(fenwick, n+1)
// }
//
// // 把下标 i 的元素增加 val
// func (f fenwick) update(i, val int) {
// for ; i < len(f); i += i & -i {
// f[i] += val
// }
// }
//
// // [1,i] 的元素和
// func (f fenwick) pre(i int) (s int) {
// for ; i > 0; i &= i - 1 {
// s += f[i]
// }
// return
// }
//
// func treeQueries(n int, edges [][]int, queries [][]int) (ans []int) {
// g := make([][]int, n+1)
// for _, e := range edges {
// x, y := e[0], e[1]
// g[x] = append(g[x], y)
// g[y] = append(g[y], x)
// }
//
// in := make([]int, n+1)
// out := make([]int, n+1)
// clock := 0
// var dfs func(int, int)
// dfs = func(x, fa int) {
// clock++
// in[x] = clock // 进来的时间
// for _, y := range g[x] {
// if y != fa {
// dfs(y, x)
// }
// }
// out[x] = clock // 离开的时间
// }
// dfs(1, 0)
//
// // 对于一条边 x-y（y 是 x 的儿子），把边权保存在 weight[y] 中
// weight := make([]int, n+1)
// diff := newFenwickTree(n)
// update := func(x, y, w int) {
// // 保证 y 是 x 的儿子
// if in[x] > in[y] {
// y = x
// }
// d := w - weight[y] // 边权的增量
// weight[y] = w
// // 把子树 y 中的最短路长度都增加 d（用差分树状数组维护）
// diff.update(in[y], d)
// diff.update(out[y]+1, -d)
// }
//
// for _, e := range edges {
// update(e[0], e[1], e[2])
// }
// for _, q := range queries {
// if q[0] == 1 {
// update(q[1], q[2], q[3])
// } else {
// ans = append(ans, diff.pre(in[q[1]]))
// }
// }
// return
// }
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.