显然把所有排列列出来，不难发现答案的第 \(i\) 位只与 \(k\) 二进制拆分后的 \(i\) 位是 0/1 和 \(i-1\) 位是 0/1 有关。
那么把 \(k\) 分解，记分解后第 \(i\) 位为 \(a_i\)，那么答案第 \(i\) 位为 a[i-1]?!a[i]:a[i]。
先考虑链如何做，是个经典问题，记 \(f_u\) 表示 \(1~u\) 中的新增的匹配数量。
显然 \(f_u\) 可以从上一次匹配的左括号位置转移，求答案就记个前缀和就好了。
考虑如何扩展到树上，记 \(f_u\) 表示根到 \(u\) 这条路径上新增的匹配数量，\(dp_u\) 表示根到 \(u\) 的匹配数量。
那么 \(dp_u=dp_{fa_u}+f_u\)。
我们维护一个栈，每次搜到一个左括号就把他压到栈里，\(f_u=0\)。
当搜到右括号时，如果栈是空的，那么 \(f_u=0\)。
否则，\(f_u=f_{fa_{stk_{tp}}}+1\)，这个转移的意思就是到 \(u\) 的新增匹配，要么是由栈顶父亲那里的匹配加上 \([stk_{tp},u]\) 这一对括号构成的，要么是 \([stk_{tp},u]\) 这对括号。
注意到回溯的时候栈里存的可能不是 \([1,u]\) 里已经匹配的，那么我们每次退栈的时候记录退栈的元素，搜完子树后再入栈。
首先不难发现一个 dp ：记 \(dp_{i,j}\) 表示划分了 \(i\) 个数，上一次划分位置是 \(j\) 的最小值。
记个前缀和转移，\(dp_{i,j}=\displaystyle \min_{sum_i-sum_k \leq sum_j-sum_i} \{dp_{k,i}+(sum_j-sum_i)^2\}\)，拿到 36 分。
考虑优化，固定 \(i\)，发现 \(j\) 变化的时候， \(k\) 也在随着变化。
那么维护一下 \(dp_{k,i}\) 的最小值就好了，拿到 64 分。
继续优化，考虑这么一个式子 \((a+b)^2 \geq a^2+b^2\)。
从这个式子我们得知尽量多分几段可以使答案更小。
所以我们每次只要找到第一个能转移的 \(k\) 进行转移就行了，记转移点为 \(f_i\)。
那么我们要求的就是最大的 \(k\) 使得 \(sum_i-sum_k \geq sum_k-sum_{f_k}\)。
移项一下，得到 \(sum_i \geq 2 \times sum_k-sum_{f_k}\)。
可以通过暴力打出决策点，发现 \(f_i\) 是单调的，即假如有 \(t<f_i\)，那么 \(t\) 绝对不是 \(f_{i+1}\)。
所以这个用单调队列维护一下即可。
不想写高精度所以用了 __int128。
原文：https://www.cnblogs.com/Lonely-233/p/15178089.html