Shortest Path in a Weighted Tree

• Preprocessing:
  • Build an adjacency list.
  • Perform a DFS from the root (node 1) to compute:
    • initial_dist[i]: The initial distance from the root to node i.
    • parent[i]: The parent of node i.
    • startTime[i] and endTime[i]: The entry and exit times for each node in the DFS traversal. This linearizes the tree such that all nodes in a subtree of v have start times in the range [startTime[v], endTime[v]].
• Data Structure:
  • Initialize a Fenwick Tree (BIT) of size N with all zeros. This BIT will store the accumulated delta changes.
• Query Processing:
  • For an update query [1, u, v, w']:
    • Determine the child node (e.g., v).
    • Calculate delta = w' - w_old.
    • This delta applies to all nodes in the subtree of v. In our linearized representation, this corresponds to the range of start times [startTime[v], endTime[v]].
    • Perform a range update on the BIT: bit.add(startTime[v], delta) and bit.add(endTime[v] + 1, -delta).
  • For a distance query [2, x]:
    • The total change in distance for node x is the sum of all deltas for ranges that include startTime[x]. This can be found with a point query on our BIT structure, which is bit.query(startTime[x]).
    • The final distance is initial_dist[x] + bit.query(startTime[x]).

This approach combines tree algorithms with a data structure to handle the queries efficiently.

1. Preprocessing: We start with a DFS from the root (node 1). During this traversal, we compute several properties for each node: its parent, its initial distance from the root, and its DFS start and end times. The start time is recorded when a node is first visited, and the end time is recorded after all its descendants have been visited. This mapping ensures that for any node v, all nodes u in its subtree satisfy startTime[v] <= startTime[u] <= endTime[v].

2. Fenwick Tree for Updates and Queries: We use a Fenwick Tree (BIT) to manage the distance modifications. A standard BIT supports point updates and prefix sum queries. To handle range updates and point queries, we can use a clever trick: to add a value delta to a range [l, r], we perform two point updates on the BIT: add(l, delta) and add(r + 1, -delta). The effect of this is that when we query the prefix sum up to an index i (query(i)), we get the sum of all deltas for ranges that start at or before i. This is exactly the total change affecting the node corresponding to time i.

3. Handling Queries:

• Update [1, u, v, w']: We find the child node (say v), calculate delta, and update the BIT at startTime[v] and endTime[v] + 1. This takes O(log N) time.
• Query [2, x]: The current distance is the initial distance plus all accumulated changes. We retrieve this by querying the BIT at startTime[x]. The result is initial_dist[x] + bit.query(startTime[x]). This also takes O(log N) time.

1import java.util.*;2 3class Solution {4    private int timer;5    private int[] parent, startTime, endTime;6    private long[] initialDist;7    private List<Map<Integer, Integer>> adj;8 9    public long[] shortestPath(int n, int[][] edges, int[][] queries) {10        adj = new ArrayList<>();11        for (int i = 0; i <= n; i++) adj.add(new HashMap<>());12        for (int[] edge : edges) {13            adj.get(edge[0]).put(edge[1], edge[2]);14            adj.get(edge[1]).put(edge[0], edge[2]);15        }16 17        parent = new int[n + 1];18        startTime = new int[n + 1];19        endTime = new int[n + 1];20        initialDist = new long[n + 1];21        timer = 0;22        dfs(1, 0, 0);23 24        FenwickTree bit = new FenwickTree(n);25        List<Long> answers = new ArrayList<>();26 27        for (int[] query : queries) {28            if (query[0] == 1) {29                int u = query[1], v = query[2], w = query[3];30                if (parent[u] == v) { // Ensure u is parent of v31                    int temp = u; u = v; v = temp;32                }33                long oldWeight = adj.get(u).get(v);34                long delta = w - oldWeight;35                adj.get(u).put(v, w);36                adj.get(v).put(u, w);37 38                bit.add(startTime[v], delta);39                bit.add(endTime[v] + 1, -delta);40            } else {41                int x = query[1];42                long currentChange = bit.query(startTime[x]);43                answers.add(initialDist[x] + currentChange);44            }45        }46 47        long[] result = new long[answers.size()];48        for (int i = 0; i < answers.size(); i++) result[i] = answers.get(i);49        return result;50    }51 52    private void dfs(int u, int p, long currentDist) {53        parent[u] = p;54        initialDist[u] = currentDist;55        startTime[u] = ++timer;56        for (Map.Entry<Integer, Integer> entry : adj.get(u).entrySet()) {57            int v = entry.getKey();58            if (v != p) {59                dfs(v, u, currentDist + entry.getValue());60            }61        }62        endTime[u] = timer;63    }64}65 66class FenwickTree {67    private long[] bit;68    private int size;69 70    public FenwickTree(int n) {71        this.size = n;72        this.bit = new long[n + 2];73    }74 75    public void add(int index, long delta) {76        for (; index <= size; index += index & -index) {77            bit[index] += delta;78        }79    }80 81    public long query(int index) {82        long sum = 0;83        for (; index > 0; index -= index & -index) {84            sum += bit[index];85        }86        return sum;87    }88}