Let's first make some observations:

1. the graph has a form of a cycle and every node may have one or more chains which are connected to it
2. the furthest node to some node u will always be a node from the cycle or a node which is the end of the longest chain connected to some node from the cycle

So with this observations we can make a segment tree where for each node u from the cycle nodes we will keep the distance from 1 to u + the length of the longest chain starting at u. Now we can easily find the furthest node to a given node u by doing two maximum queries on this segment tree — the first one will be in the interval [u, n] so if the max there is x then the distance to furthest node will be x — distance from 1 to u. The other query will be in the interval [1, u — 1] and if the maximum there is y then the distance to the furthest node will be distance from u to 1 + x. So you choose the maximum between these two values and voilà there it is the furthest node. You can keep not only the distances in the segment tree but also the node indices so that you find the node itself not only the distance to it.

Now the other question is how to keep the longest chains for each node and also be able to make insert and delete queries to this chains. As we said we will only delete ending nodes in this chains and also we will only insert at the end of some chain. So we can maintain a priority queue for each node from the cycle and when we have an insert query we just take the top of the queue x and then insert in the queue x+w where w is the weight of the new edge. When we have a delete query we just need to remove the top of the queue.

The complexity is .

Here is my code. Hope it was helpful. If you have some questions feel free to ask.

2-3 days.