Doubt in editorial solution

Правка en1, от Roronoa__Zoro, 2023-12-24 12:18:09

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:

Spoiler

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Roronoa__Zoro 2023-12-24 12:20:11 5902
en1 Английский Roronoa__Zoro 2023-12-24 12:18:09 7418 Initial revision (published)