Explanation

First, we need to divide queries into two types: those that require us to jump to the root, and those that don't require such. Let's consider a query for the shortest path $u \rightarrow v$.

Case 1: $u$ is an ancestor of $v$

The optimal solution is for our path to just walk downwards from $u$ to $v$. This is equivalent to $\texttt{dist}(1 \rightarrow v) - \texttt{dist}(1 \rightarrow u)$, where $1$ is the root of our tree. To answer these queries, we use the method described in this editorial.

Case 2: $u$ is not an ancestor of $v$

In this scenario, our path from $u$ to $v$ has the following structure.

1. First, we traverse down to some node in the subtree of $u$
2. Using the back edge at our chosen node, we jump to node $1$.
3. Finally, we walk down to node $v$

We can use the same code for case 1 to calculate $\texttt{dist}(1 \rightarrow v)$. However, it isn't exactly clear how we should figure out the best node to pick in the subtree of $u$ to jump from. Let the node we traverse down to be $x$. Then, the cost of using node $x$ to jump to the root is:

Here, $\texttt{back}[x]$ refers to the cost of jumping from $x$ to the root. Using the same idea from case 1, we can change our expression a bit.

The distance from the root to node $u$ is fixed here. Thus, we want to find the best value of $\texttt{dist}(1 \rightarrow x) + \texttt{back}[x]$ within the subtree of $u$. To do this, we use Euler Tour to flatten our tree, and then use a lazy segment tree to answer our queries.

Our segment tree must support range addition and range minimum. For more information on how to implement it, refer to the Range Updates Range Queries module.

Handling Updates

If the edge we are updating is from node $u$ to node $1$, then it only affects the value in our segment tree for node $u$. Thus, we do a point update on the node in question.

In the case that the edge we are updating isn't from some node to the root, then it changes all the values inside the subtree it affects. Let's have the edge affected connect node $u$ and node $v$, with the difference in weight being $w$. Then, we must do the following.

• Change the distances in the subtree of $v$ by $w$
• Change the value of $\texttt{dist}(1 \rightarrow x) + \texttt{back}[x]$ by $w$

In my code, this boils down to updating the binary indexed tree handling the root to node distances, and updating the segment tree containing the value of $\texttt{dist}(1 \rightarrow x) + \texttt{back}[x]$ for every node.

Implementation

Time Complexity: $\mathcal{O}((N+Q)\log{N})$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

 Code Snippet: Lazy Segment Tree (from the module) (Click to expand)

 Code Snippet: BIT (from the module) (Click to expand)

int main() {