Shortest Path in a Weighted Tree

The key observation for an efficient solution is that an edge weight update affects all nodes in a specific subtree uniformly. This pattern of "range updates" (on a subtree) and "point queries" (for a node's distance) suggests using a specialized data structure. By linearizing the tree using DFS start and end times, we can map the subtree updates to range updates on an array. A Fenwick Tree (or a Segment Tree) is an excellent tool for handling these operations efficiently.

• 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.

import java.util.*;

class Solution {
    private int timer;
    private int[] parent, startTime, endTime;
    private long[] initialDist;
    private List<Map<Integer, Integer>> adj;

    public long[] shortestPath(int n, int[][] edges, int[][] queries) {
        adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new HashMap<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).put(edge[1], edge[2]);
            adj.get(edge[1]).put(edge[0], edge[2]);
        }

        parent = new int[n + 1];
        startTime = new int[n + 1];
        endTime = new int[n + 1];
        initialDist = new long[n + 1];
        timer = 0;
        dfs(1, 0, 0);

        FenwickTree bit = new FenwickTree(n);
        List<Long> answers = new ArrayList<>();

        for (int[] query : queries) {
            if (query[0] == 1) {
                int u = query[1], v = query[2], w = query[3];
                if (parent[u] == v) { // Ensure u is parent of v
                    int temp = u; u = v; v = temp;
                }
                long oldWeight = adj.get(u).get(v);
                long delta = w - oldWeight;
                adj.get(u).put(v, w);
                adj.get(v).put(u, w);

                bit.add(startTime[v], delta);
                bit.add(endTime[v] + 1, -delta);
            } else {
                int x = query[1];
                long currentChange = bit.query(startTime[x]);
                answers.add(initialDist[x] + currentChange);
            }
        }

        long[] result = new long[answers.size()];
        for (int i = 0; i < answers.size(); i++) result[i] = answers.get(i);
        return result;
    }

    private void dfs(int u, int p, long currentDist) {
        parent[u] = p;
        initialDist[u] = currentDist;
        startTime[u] = ++timer;
        for (Map.Entry<Integer, Integer> entry : adj.get(u).entrySet()) {
            int v = entry.getKey();
            if (v != p) {
                dfs(v, u, currentDist + entry.getValue());
            }
        }
        endTime[u] = timer;
    }
}

class FenwickTree {
    private long[] bit;
    private int size;

    public FenwickTree(int n) {
        this.size = n;
        this.bit = new long[n + 2];
    }

    public void add(int index, long delta) {
        for (; index <= size; index += index & -index) {
            bit[index] += delta;
        }
    }

    public long query(int index) {
        long sum = 0;
        for (; index > 0; index -= index & -index) {
            sum += bit[index];
        }
        return sum;
    }
}