1. Pseudotree is basically a single cycle with trees attached to its vertexes.
2. Find the cycle with DFS. You run usual DFS and when it finds edge going to an already visited vertex (and not previous vertex) — here is the cycle.
3. Decompose pseudo tree in cycle and trees.
4. Answer either goes through cycle's edges or not. If it does not, it's completely inside some tree. If it does, then it starts in the deepest leaf of one tree and ends in the deepest leaf of another tree.
5. The first part is the problem you already know how to solve: find diameter of the tree.
6. The second part is more tricky. It can be reformulated as follows: you have an array of K elements, where a_i is the depth of i-th tree. You have to find such i and j that a_i + a + j + min(|i - j|, K - |i - j|) is maximized.
7. The last problem can be solved with improved brute force: run down i and assume that corresponding j can be found on the right of i (i.e. between i + 1 and something like ). Now you have a bunch of requests of the form "find maximal j + a_j on this subsegment". It can be solved with arbitrary RMQ solution. That would result if for the whole solution.

Was printing my answer too slow (my english skill is so weak). However, decide to post it.

How does a tree with one extra egde look like? It's a simple cycle with trees rooted at this cycle's nodes. It can be two cases:

1) Simple — diameter lies inside one of this rooted trees. Easy to compute the answer.

2) Main one — diameter enters cycle at vertex u and leaves at v. Then the answer is the shortest of two pathes in cycle between u and v, plus h_u, plus h_v, where's h_u is max height of u's rooted tree.

Let's enumerate nodes in our cycle as 0, 1, ... c - 1 (c — cycle length). Now suppose that diameter enters cycle at node 0. What's the answer in this case? It's h₀ + max(h₁ + 1, h₂ + 2, h₃ + 3, ... h_x + x) where x is number around and then h₀ + max(h_x + 1 + (x - 1), h_x + 2 + (x - 2), ... h_c - 1 + 1).

Let's put values for one half of the cycle (h₁ + 1, h₂ + 2, ... h_x + x) in some data structure (and the second half's values to another copy of this structure). What does change when we switch from node 0 to node 1? We need to remove one value from this structrure (h₁ + 1), then decrease all values by 1, add new value (h_x + 1 + x) and find maximum of them.

So we need a data structure which provides following operations: add/remove elements, decrease all elements by the same number and get maximum element. It's not hard data structure's task and can be done via simple heap/set with some additional easy manipulations to support decreasing. The key observation is — if all elements are decreased at once — maximum element remains the same, only his value is decreased.

The complexity for each DS operation will be O(log c), so overall complexity will be O(n + c log c). It can be futher reduced to O(1) for operation (and overall O(n)) with using queue that supports its maximum instead of heap/set (because we remove only head elements and add tail ones, not random ones).

P.S. Can you provide a link for this task?

I don't know how to prove this but I heard that the same approach for trees can be used to find the diameter of a tree with an extra edge. (Run BFS from an arbitrary vertex, find the farthest vertex and run BFS from this vertex). This works in O(n). I think I heard about this from tehqin's Algorithms Live.

Auto comment: topic has been updated by vamaddur (previous revision, new revision, compare).