Choosing Two Paths
Contest: Educational Codeforces Round 53 (Rated for Div. 2)
Difficulty rating: 2500
Tags: dfs and similar, dp, greedy, trees

You are given an undirected unweighted tree consisting of $$$n$$$ vertices.

An undirected tree is a connected undirected graph with $$$n - 1$$$ edges.

Your task is to choose two pairs of vertices of this tree (all the chosen vertices should be distinct) $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ in such a way that neither $$$x_1$$$ nor $$$y_1$$$ belong to the simple path from $$$x_2$$$ to $$$y_2$$$ and vice versa (neither $$$x_2$$$ nor $$$y_2$$$ should not belong to the simple path from $$$x_1$$$ to $$$y_1$$$).

It is guaranteed that it is possible to choose such pairs for the given tree.

Among all possible ways to choose such pairs you have to choose one with the maximum number of common vertices between paths from $$$x_1$$$ to $$$y_1$$$ and from $$$x_2$$$ to $$$y_2$$$. And among all such pairs you have to choose one with the maximum total length of these two paths.

It is guaranteed that the answer with at least two common vertices exists for the given tree.

The length of the path is the number of edges in it.

The simple path is the path that visits each vertex at most once.

Input format:
The first line contains an integer $$$n$$$ — the number of vertices in the tree ($$$6 \le n \le 2 \cdot 10^5$$$).

Each of the next $$$n - 1$$$ lines describes the edges of the tree.

Edge $$$i$$$ is denoted by two integers $$$u_i$$$ and $$$v_i$$$, the labels of vertices it connects ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$).

It is guaranteed that the given edges form a tree.

It is guaranteed that the answer with at least two common vertices exists for the given tree.

Output format:
Print any two pairs of vertices satisfying the conditions described in the problem statement.

It is guaranteed that it is possible to choose such pairs for the given tree.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The picture corresponding to the first example:

The intersection of two paths is $$$2$$$ (vertices $$$1$$$ and $$$4$$$) and the total length is $$$4 + 3 = 7$$$.

The picture corresponding to the second example:

The intersection of two paths is $$$2$$$ (vertices $$$3$$$ and $$$4$$$) and the total length is $$$5 + 3 = 8$$$.

The picture corresponding to the third example:

The intersection of two paths is $$$3$$$ (vertices $$$2$$$, $$$7$$$ and $$$8$$$) and the total length is $$$5 + 5 = 10$$$.

The picture corresponding to the fourth example:

The intersection of two paths is $$$5$$$ (vertices $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ and $$$5$$$) and the total length is $$$6 + 6 = 12$$$.

Example input:
7
1 4
1 5
1 6
2 3
2 4
4 7

Example output:
3 6
7 5

Example input:
9
9 3
3 5
1 2
4 3
4 7
1 7
4 6
3 8

Example output:
2 9
6 8

Editorial:
Firstly, let's call a path from $$$u$$$ to $$$v$$$ good, if $$$u$$$ is a leaf, $$$v$$$ is a vertex of degree at least $$$3$$$ (the number of their neighbors is at least $$$3$$$) and there are no other vertices of degree at least $$$3$$$ on this path expect the vertex $$$v$$$.
The first step of the solution is to remove all the good paths from $$$u$$$ to $$$v$$$ (but we should not remove the vertex $$$v$$$) and remember for each vertex $$$v$$$ the sum of two maximum lengths of good paths which end in the vertex $$$v$$$. Let this value for the vertex $$$v$$$ be $$$val_v$$$. For example, if for some vertex $$$v$$$ there are $$$3$$$ good paths with end in it of lengths $$$2$$$, $$$3$$$ and $$$5$$$ correspondingly, then $$$val_v$$$ will be $$$5 + 3 = 8$$$.
Okay, it is easy to see that the maximum intersection of two paths in the answer will be equal to the length of the diameter of the obtained tree. But we can not take any diameter of this tree and call it the answer because of the second constraint: we need to find some diameter from $$$x$$$ to $$$y$$$ such that the sum $$$val_x + val_y$$$ is maximum possible. How do we do that?
There is such an awesome (and well-known) fact that the center of a tree belongs to all diameters of this tree. Let's root the tree by the center of a tree (if the length of the diameter is odd (the center of a tree is an edge) then let's root the tree by any end of this edge, it does not matter).
There is one case when the length of the diameter is $$$1$$$ but it is pretty trivial to handle it.
Now our problem is to find two neighbors of the root of the new tree such that in their subtrees are vertices which form some diameter of this tree and the sum of values of these vertices is maximum possible. Let's calculate the vertex with the maximum distance from a root (and with the maximum possible $$$val_v$$$ for equals distances) by simple DFS for each neighbor of a root. It can be done in $$$O(n)$$$ and the last part is to find two maximums of this list, it also can be done in $$$O(n)$$$ or $$$O(n \log n)$$$, depends on implementation.