Hello, my basic thinking is if I can connect all elements in x iterations. then x+1, x+2... can be ignored.
https://mirror.codeforces.com/contest/1830/submission/234754662
https://mirror.codeforces.com/contest/1830/submission/234753813
This is my submission in python and c++ one I've converted using help from gpt.
Thank you for reply.
cond()
has complexity $$$O(n^2 \log n)$$$.If the tree is a line, and $$$m = n$$$, you add one edge for each $$$i$$$, and you spend $$$O(n \log n)$$$ for each $$$i$$$, so you spend $$$O(n^2 \log n)$$$ in total.
A faster solution would be just calling
cond()
once, with $$$m = n$$$, and return $$$i$$$ if the set size is $$$n$$$, but it's still too slow.Because this
works in $$$O(m \cdot n\log n)$$$ or, in general, $$$\Omega(ans \cdot n\log n)$$$ (that is, the
cond()
complexity is $$$O(n^2\log n)$$$, because $$$ans = O(n)$$$)