满二叉树$O(n\log n)$和链$O(n)$的复杂度基本卡不了这个算法，但是使用树套树可以把它卡到$O(n(\log(n/k)*k))$，即$O(n\times(k\log(n)-k\log(k)))$ 。

对于构造$2^{20}$个点（略大于$10^6$）的一棵树，可以分成 $2^{10}$ 层，每层一棵 $2^{10}$ 个节点的树。

先构建 $1024$ 棵满二叉树，然后用1023条边让他们链接，每棵树之间，上面一棵树的其中一个叶子节点和下面那棵树的根节点连一条边。

时间复杂度就可以被卡到$O(10^6 \times 10\times 20-10\times 10)=O(10^6\times 100)=O(10^8)$ 。

可以卡常数较大的程序。

这个数据不知道可不可行（？！）