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

Revision en1, by 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.

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!

Tags trees, diameter


  Rev. Lang. By When Δ Comment
en1 English TheOpChicken123 2022-06-24 12:57:55 773 Initial revision (published)