So in this problem 1294F - Three Paths on a Tree. The editorial solution is this :
Spoiler
Suppose our tree has 23 nodes. Let the diameter contains all the node b/w 1 and 20 (take in increasing order for simplicity). Lets take a branch from node 5 which contains the remaining nodes . So according to the editorial we use multi-source bfs and find the node which is at farthest distance . The node that will be farthest will be around node 9 or 10. But if we take this as third node the result will be (1 , 20 , (9 or 10)) but this will not increase the result we will still get 19 edges as our answer. Rather we should take a branch with is at max distance from any node on diameter. I tried this approach but it is giving MLE . Here is the code:
Auto comment: topic has been updated by Roronoa__Zoro (previous revision, new revision, compare).
That's correct. You misinterpreted the editorial. This is exactly what the editorial is asking you to compute. One way to compute this value is to run multiple BFS/DFS from each node on the diameter, which works, but is inefficient. A clever solution is to run a multi source BFS with the source as ALL nodes on the diameter. This is what the editorial means by multi source BFS (I think you got it confused with running multi source BFS from the endpoints of the diameter only).
This is incorrect. If nodes 9/10 are part of the diameter, their distance would be zero in a multi source BFS initiated from all vertices on the diameter.
You can find my analysis and code on CF Step
Wowww... Nice Explanation . Thank you. But can u please explain why my code is giving MLE