Shortest Path in a Weighted Tree

This problem requires efficiently answering shortest path queries on a dynamically weighted tree. Flatten the tree with an Euler tour and maintain edge states to quickly update distances. Using depth-first traversal combined with segment or binary indexed trees allows handling queries in logarithmic time per operation, reducing naive recalculation overhead and ensuring correctness even with frequent edge weight updates.

Problem Statement

Given a weighted undirected tree rooted at node 1 with n nodes numbered from 1 to n, represented as edges where each edge contains two nodes and a weight, compute shortest paths for dynamic queries. Each query either updates an edge weight or asks for the shortest path from the root to a specified node.

You must return an array of integers representing the shortest path distances for all type-2 queries. Efficient traversal and state tracking are necessary due to potentially high n and q values. The tree structure guarantees no cycles, and updates only modify existing edge weights.

Examples

Example 1

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

Output: [7,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]

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]

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

• 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

Solution Approach

Flatten the tree with Euler Tour

Perform a DFS from the root to record entry and exit times for each node, creating a linear representation of the tree. This allows mapping subtree ranges to array segments for efficient segment or binary indexed tree operations.

Maintain distances with a segment or binary indexed tree

Store cumulative distances from the root in a segment tree or BIT. Update edge weights by adjusting the corresponding range, and query distances in O(log n) time. This ensures dynamic updates do not require full traversal each time.

Process queries efficiently

For type-1 queries, update the edge weight in the range representing the subtree. For type-2 queries, directly read the distance from the root to the target node using the flattened structure. Handle all queries sequentially to maintain consistency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on tree flattening O(n) and O(log n) per query using segment trees or BIT. Space complexity includes storing the tree structure, Euler tour indices, and segment/BIT data structures, totaling O(n).

What Interviewers Usually Probe

• Expect questions on Euler tour flattening and subtree segment mapping.
• Be ready to explain how dynamic edge updates affect distance computation.
• Demonstrate understanding of combining DFS traversal with range-based data structures.

Common Pitfalls or Variants

Common pitfalls

• Not correctly mapping subtree ranges in the Euler tour leading to wrong updates.
• Failing to handle cumulative distance updates for dynamic edge weight changes.
• Assuming static edge weights and trying naive traversal for every query.

Follow-up variants

• Queries may only ask distances without edge updates, simplifying to a standard DFS.
• Tree could be rooted at any node, requiring rerooting techniques for correct distances.
• Weighted tree could allow negative weights, requiring careful distance propagation to avoid incorrect sums.

FAQ

What is the primary pattern used in Shortest Path in a Weighted Tree?

The problem relies on binary-tree traversal combined with state tracking, using an Euler tour to flatten the tree for efficient range queries.

How do I handle type-1 update queries efficiently?

Use the Euler tour to map the affected subtree to a contiguous array segment, then update the corresponding range in a segment tree or BIT.

Can I use simple DFS for each type-2 query?

DFS for every query is too slow for large n and q. Instead, precompute distances and update them with range-based structures for O(log n) query time.

What data structures are recommended for this problem?

Segment trees or binary indexed trees work best for maintaining cumulative distances and supporting range updates efficiently.

Why is flattening the tree necessary?

Flattening with an Euler tour maps subtrees to contiguous array segments, allowing fast updates and queries without repeated traversal.