梦回 CJ LCOI 奶牛了咋办。
注意到若树的形态非链，一定可以通过一次操作使得链的长度至少增加 \(1\)，因此可以推断出最终形态一定为链并且操作次数上界为 \(n - 2\)。
不妨思考一些特例情况看什么时候可以取到 \(n - 2\)，不难发现当根的右儿子只有一个的时候就可以，并且此时左子树形态任意都行，这是因为左子树可以递归花费最多的操作次数变成链，然后类似 Splay 旋转将右儿子慢慢转下去。
预处理卡特兰数和阶乘分配标号即可。
提示我们遇到这种题先分析上界再考察特殊形态，最后看看能规约成什么样子。