Luogu P5994 [PA2014]Kuglarz（ XOR thinking +MST）

The question ：

There are... On the magician's desk $n$ A line of cups , The number is $1,2,\dots ,n$, Some of the cups have a small ball under them , If you can guess exactly which cups , You can get the prize .

cost $c_{ij}$ element , The magician will tell you the cup $i,i+1,\dots ,j$ The parity of the total number of balls hidden underneath .

Take the best inquiry strategy , At least how much do you need to spend , To make sure you know which cups have balls under them ？

Ideas ：
MST