洛谷P2962题解

题面

看到 \(n \leq 35\) ，这是一个非常小的数据，但是 \(O(2^n)\) 的暴力跑不过去，所以考虑玄学做法 \(\text{Meet in Middle}\) 。就是先做左边，然后做右边的时候顺便和左边合并。

考虑到每个点最多进行一次操作（两次操作回源没用），所以对于每个点只有操作和不操作两种选择。

代码中，\(mp\) 数组记录到当前状态的最小步数， \(p\) 数组表示操作当前节点时所有会改变的节点。
所以可以看到这个题目还用了状态压缩的思想。

代码