Blog : Three Paths on a Tree

Picked this 2000 rated problem randomly from CF problemset with the “Tree” tag.

If the problem had instead asked for maximizing the edge count between 2 distinct vertices, it would’ve been equivalent to finding the longest path in a tree. In other words, the Diameter of the tree. Hence, I should first practice the problem Tree Diameter from CSES first. Regardless of whether the 2 problems are connected or not, it’s a good learning opportunity for me.

I’ve passively heard about the technique of finding the diameter of a tree: You run a BFS from any node, find the farthest node, say src, then run another BFS from src to find the farthest node from src, say target. The distance between src and target is the tree’s diameter. However, I’ve never implemented it nor wondered about the intuition or correctness. Maybe I might need to read some blogs to get a better understanding.

Solved the tree diameter problem on CSES after skimming this tutorial by TheScrasse. That’s a great tutorial, especially the image of the diameter and the interpretation that a tree can be represented as several forests that are hanging by the diameter. This actually helped me to get closer to the solution of this problem.

Intutitively, the answer should contain both end of the diameter, and the forest with the maximum height. Out of the 3 vertices, consider the pair with the maximum dist between them. WLOG, suppose it’s node a and b. Let’s hang the entire tree on the path from node a to node b. It’s easy to see that the node c should not lie in the path, and should instead be on the deepest forest. Hence, we should pick the diameter as the horizontal line and then select the deepest forest.

How do we find the deepest forest quickly? This required some thinking, but I was able to come up with the Multi Source BFS trick. Instead of doing a BFS one by one from each node on the path between a and b, let’s do a single BFS with all the paths from a to b as source. Any farthest node on the resulting BFS tree is our answer.

I submitted this approach, but I’m getting wrong answer on TC39. This probably means that my idea is correct, and there’s a bug in implementation. The checker logs say

wrong answer Printed vertices should be distinct

I need to debug how could I possibly be printing duplicate nodes, since the problem mentions n >= 3.

Oh, it just struck my mind that if the tree is a straight line, then while running the multi source BFS, there would be no forest and all nodes would have dist equal to zero. Hence, we should not just randomly select the first vertex with max dist.

Yay! Solved the problem after this fix. This was a nice problem to learn tricks such as the diameter of a tree, forests hanging on the diameter, BFS, multi source BFS, tracing the path in BFS via parent array.

I have still not solved CSES : Tree Distances 1 although I know the idea that the one of the diameter’s endpoint will always be the farthest node. I can’t prove that. Skipping the problem for now, might come back to it later.