题解：CF1951H Thanos Snap

· · 题解

考虑二分转为判定性问题，变成 01 串，Alice 的目标是有 1。

在第 x 层能赢，则必然有 x 内有至少 2^{t-x} 个点，不妨归纳证明：

考虑 dp，预留把这个点以内的子树操作到能赢的最小步数。

转移有：dp_u=\max(\{dp_{ls}+dp_{rs}-1,2^{t-x}-sum_u,0\})，其中 sum_u 为 u 内合法点数。因为换进来的点可以手动选择换在左边还是右边，因此可以直接取 \max。

https://codeforces.com/contest/1951/submission/345133511。