Let $G$ be a undirected edge-weighted tree, where all edge weights are positive. A move of an edge $\{u,v\} \in E(G)$ is the operation of deletion of $\{u,v\}$ and the addition of a new edge $\{x,y\}$, where $x,y \in V(G)$. Intuitively, we can think of the move meaning the deletion of an edge, and the re-insertion of it between two new vertices.
Now, given $G$, our task is to maximize the weight of a longest path in $G$ by a single move with the constraint that the newly obtained graph $G'$ remains a tree. An example is given below:
The longest path is E-B-C-D with weight 18 at the initial state. But if we move B-C to E-F we get a longest path A-B-E-F-C-D with weight 23.
One could rely on brute force, which is a feasible approach: remove an edge, try putting it between two vertices, check if a graph is still acyclic, find the longest path, try another pair of vertices, try another edge. You will end up with enumerating all possible acyclic graphs.
My question is the following: could we do better than brute-forcing all possibilities?
