Find maximum diameter of a tree given that you can remove one edge and replace that edge anywhere.

Правка en1, от TheOpChicken123, 2022-06-24 12:57:55

Hey all, I have been struggling with this question for quite a while now (almost three months) and there are no solutions that I can find online. It is from the Singaporean NOI qualification 2022 qualification test. The problem is described in the title —

given a tree, find the maximum diameter of the tree if you can remove one edge, and put that edge anywhere else. However, in the end, it must remain a tree. This is the link to the problem which also contains two testcases. https://codebreaker.xyz/problem/treecutting

I have been able to do it in O(n*n) by brute force but it is too slow. Can anyone help? Any help will be greatly appreciated. Thank you!

Теги trees, diameter

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский TheOpChicken123 2022-06-24 12:57:55 773 Initial revision (published)