This problem is from 2018 ICPC North American Qualifier Contest. Here is the link: LCM Tree.

I tried to solve this problem using bitset DP. Each number from $$$S$$$ is a candidate for building LCM Tree, initially, only the bit of greatest element is on. Every time we append two nodes with $$$lcm{(S_j, S_k)} = S_i$$$ to the bit which is on and turn off that bit. However, if multiple numbers have the same value, my approach will fail. I'm wondering if this approach can actually work on this problem or there is a better approach?