首先将原树重链剖分，将结点编号换成 dfs 序，这样重链编号就连续了。对每个点 i，记 sn_i 为重儿子，sz_i 为子树大小，w_i=sz_i-sz_{sn_i} 为一个权值。对于每一条重链，建出一个二叉树的结构，做法是找到当前区间的带权中点（第一个满足 w 的前缀和乘 2 大于 w 的总和的点），将这个点作为根，递归左右区间。对于一条重链，设链头为 i，建出的二叉树的根为 j，则新树上 j 的父亲为原树上 i 的父亲。
我们称二叉树上的边为实边，j 向 i 的父亲连的边为虚边。根据树剖的性质，一个点跳到根只会跳 \log n 次虚边。记 sum 为新树上当前点子树内和当前点属于同一重链的 w_i 之和，若跳实边则 sum 至少翻倍，若跳虚边则 sum 不会减少。根据 w_i 的定义，一条重链的 w_i 之和为链头的子树大小，所以 sum 至多达到 n。于是新树的树高为 \log n 级别。