# On Finding Optimal (Dynamic) Arborescences
## 3 Optimal Dynamic Arborescences
### ATree Data Structure  
ATree is an extension of the forest \(F\) data structure presented in Section 2.2. The nodes of the ATree maintain the following records: the edge of \(G\), the node \(N\), represents \(\texttt{EDGE}(N)\); the cost of the edge at the time it was selected is represented by \(\texttt{w}_{N}\); its parent is represented by \(\texttt{PARENT}(N)\); the list of its children is represented by \(\texttt{CHILDREN}(N)\); its kind (simple or contracted) is measured; the list of contracted edges during the creation of the super node is documented; the edge of maximum weight in the cycle \(\texttt{e}_{max}\) is measured; and its weight \(\texttt{w}_{max}\) is measured. In an edge deletion, the edge is removed from the contracted edges list into which it belongs. In the process of decomposing and reconstructing the ATree, the set of edges \(E^{\prime}\) corresponds to the concatenation of the lists of contracted edges associated with each deleted ATree node. And, we need to update the weight of every edge \((u,v)\) of \(E^{\prime}\). Let \(\mathrm{N}_{v}^{s}\) be the simple node whose contracted edges contain \((u,v)\). The new weight \(w^{\prime}(u,v)\) is \(w^{\prime}(u,v)=w(u,v)-\sum_{N\in P}w_{N}\), where \(P\) is the set of ancestors of \(\mathrm{N}_{v}^{s}\), \(w(u,v)\) is the original weight, and \(w_{N}\) the weight of the edge represented by \(N\) at the time it was selected. We run a BFS on each tree to find the subtracted sum \(r_{i}\) of each simple node \(\mathrm{N}_{i}^{s}\) in \(O(n)\) time. Then, we scan the edges \(e\) to assign the reduced cost \(w^{\prime}(e)=w(e)-r_{i}\). While adding an edge \((u,v)\), we look for a candidate node to replace in the ATree. The process starts with \(\mathrm{N}_{v}^{s}\), and it checks every ancestor until the root is inspected or if a node \(N\) verifies \(w^{\prime}(\texttt{EDGE}(N))>w^{\prime}(u,v)\), where \(w^{\prime}(\texttt{EDGE}(N))\) denotes the reduced cost of the edge presented by \(N\). If the root is reached without verifying the condition, we insert \((u,v)\) in the contracted edges list of the lowest common ancestor of \(\mathrm{N}_{v}^{s}\) and \(\mathrm{N}_{u}^{s}\). If the condition is met, we find a candidate node \(N\) where \((u,v)\) could be added, but we must determine if \((u,v)\) is safe to be added. We check if \(\mathrm{N}_{u}^{s}\) is already present with a BFS in the subtree of root \(N\). If we find \(\mathrm{N}_{u}^{s}\), and we insert \((u,v)\) in the contracted edges list of the lowest common ancestor of \(\mathrm{N}_{v}^{s}\) and \(\mathrm{N}_{u}^{s}\). Otherwise, we engage a virtual deletion of \(\texttt{EDGE}(N)\) (the edge is not deleted, but the ATree is decomposed); then, we build the graph \(G^{\prime}=(V^{\prime},E^{\prime}\cup\{(u,v)\})\) and execute the [PERSON] algorithm for \(G^{\prime}\) as mentioned before. The pseudocode for finding a candidate is detailed in Algorithm 6, where \((u,v)\) is the edge to be inserted. Figure 14: We add the edge \((2,0)\) with weight 2 to the graph (**(a)**: edge represented in red). The process starts with the analysis of node \(\mathrm{N}_{0}^{s}\), which represents edge \((3,0)\) with weight 1. The vertex \((2,0)\) cannot replace the \(\mathrm{N}_{0}^{s}\) edge, as it is heavier. Then, the \(\mathrm{N}_{0}^{s}\) parent is examined, \(\mathrm{N}_{0,1,3}^{c}\). The corresponding edge is heavier than \((2,0)\), and \(\mathrm{N}_{2}^{s}\) is not present in its subtree. Then, \((2,0)\) should replace this node, and \(\mathrm{N}_{0,1,3}^{c}\) and its ancestors are virtually deleted (**(b)**: nodes represented in white). The [PERSON] algorithm is executed on the remaining nodes (represented in gray). ```
\(nodeF=N_{v}^{s}\) if\(w(\texttt{EDGE}(nodeF))>w(u,v)\)then return\(nodeF\) endif \(S\leftarrow\emptyset\)\(\triangleright\) Let \(S\) be a set. while\(nodeF\
eq null\)do \(S=S\cup\{nodeF\})\) \(nodeF=\texttt{PARENT}(nodeF)\) endwhile  Let \(L\) be a LIFO containing the nodes in cycle creation order.