Hints : Three Paths on a Tree

Hint 1 ↕

Solve an easier version of the problem first

Given nodes a and b, come up with a Linear time algorithm to compute node c such that the number of edges on atleast one of the three paths is maximised.

Hint 2 ↕

Visualise the tree as a straight line, with endpoints as a and b. Then, hang the remaining vertices on that rod. Refer to the image in the next hint for a visualization.

Hint 3 ↕

Intuitively, where should should vertex c be? And how to find it optimally?

Hint 4 ↕

The deepest node in the forest is node c.

One way to find such a vertex c is to start a BFS from each node lying on the rod (path from a --> b). Then, pick the node with the maximum height amongst them. How to speed it up?

Hint 5 ↕

Answer: Multi Source BFS

Hint 6 ↕

Run a multi source BFS with all nodes on the straight line as the source. This would give you the depth of each node in the forest.

How to compute all nodes lying on the path from a to b?

Hint 7 ↕

How to compute all nodes lying on the path from a to b?

Answer: Start a BFS from point a, and maintain parent pointers. Then, climb the parent array, starting from b until you reach node a.

Hint 8 ↕

Now that we have solved the easy version, let’s focus on the original problem. What nodes are best suitable for candidates of a and b?

Hint 9 ↕

Intuitively, the end points of the diameter are the best candidates. It can give you the longest rod on which you can hang other nodes. Read this tutorial to learn about Tree Diameter and how to compute it.

Solve CSES: Tree Diameter

(Optional): Solve CSES: Tree Distances 1

Hint 10 ↕

Start a BFS with a random node. Get the farthest vertex, say a. This is one endpoint of the diameter.
Start a BFS from node a and get the farthest node, say b. This is the other end of the diameter.
Start a multi source BFS with all nodes on the path from a to b as source. Then, the deepest node in the tree is c.

If you’re getting a WA with the above approach, read the next hint for a catch.

Hint 11 ↕

What happens if the tree is a straight line? How to ensure that node c is different from node a and b after multi source BFS? Note that distance of all nodes would be zero in multi source BFS.