本题多篇题解和帖子中都提到了爆搜能过，而且还挺快，于是抱怨数据过水。事实上，这只是看起来是$O(n^2)$的，我们将要证明这其实是 $O(nlogn)$ 的。

对于一棵满二叉树，我们从每个节点出发遍历这个结点的子树。

对于第一层的结点，子树大小为$O(n)$ ，只有一个结点，所以时间是$O(n)$ 。

对于第二层的结点，子树大小$O(\frac n2)$ ，有两个结点，时间开销仍然是$O(\frac n2)\times 2=O(n)$。

类似地，从任何一层出发遍历的时间都是$O(n)$ 。

而树一共只有$O(logn)$ 层。所以总时间应该是 $O(n)\times O(logn) =O(nlogn)$ 。

$\operatorname{QED}$