题解

Bubble Cup 9 - Finals [Online Mirror] B. R3D3’s Summer Adventure

很显然这是一棵树，而且$01$个数是相同的。
想一下如果要求$O(n\log n)$做法的话，我们有一个很好的贪心做法，就是最开始一棵空树，然后每次选权值最小的链，将其扩展出两个孩子。
仔细思考一下这个做法，我们发现假如我们给树上每个节点的权值定义为到根权值和，那么除去所有的叶子结点，其他的非叶子结点可以看成是权值从小到大依次出现的，因为根据前面的那个贪心做法，我们是从小到大扩展了所有的非叶子结点。
那么考虑非叶子结点权值和，假设根节点权值为$0$，那么还要加上$(n-1)\cdot (c _ 0 + c _ 1)$才能满足要求（因为考虑以某个节点为根的子树，那么他自己的贡献被计算了子树大小次，然而叶子结点是=非叶子结点+1的，因为这个1的差距我们要加上这个东西）。
那么现在我们的问题就是求出权值从小到大的$n-1$个点的和即可，假设$c _ 0 < c _ 1$。
考虑二分一下最大的权值，假设为$C$，求出所有$\leq C$的结点个数，找到第一个$\geq n-1$的即可。
根据贪心原理，那么一条链上$c _ 1$的个数$i$不会超过$\log _ 2n$，因此我们可以枚举$c _ 1$的个数，然后求出$c _ 0$个数的上界$j=\left\lfloor \frac{C-i\cdot c _ 1}{c _ 0} \right\rfloor$，求出这个东西：

$$calc(C) = \sum _ {i = 0} ^ {\log _ 2n} \sum _ {k = 0} ^ {j}\binom {i + k} {i}=\sum _ {i = 0} ^ {\log _ 2n}\binom {i + j + 1} {i + 1}$$
求出了最大权值$max$后，那么我们的答案就分成了两部分，一部分是等于$max$的，另一部分是小于$max$的。
等于的很好算，就是$(n-1-calc(max - 1))\cdot max$。
考虑小于的，可以写成：
$$\sum _ {i = 0} ^ {\log _ 2 n}\sum _ {k = 0} ^ {j}(i\cdot c _ 1 + k \cdot c _ 0)\binom{i + k}{i}=c _ 1\cdot \sum _ {i = 0} ^ {\log _ 2 n}i\cdot \binom {i + j + 1} {i + 1} + c _ 0 \cdot \sum _ {i = 0} ^ {\log _ 2 n}(i + 1)\cdot \binom{i + j + 1}{i + 2}$$
嗯，就是这样了。