Uber SDE 2 Phone Interview: Union Find Graph Optimization Challenge

I shared the brute-force approach in the first 5 minutes, then spent the next 40 minutes grinding for the optimal solution he kept hinting it can be better. When I couldn't quite nail the optimization