Day1

不是这什么b玩意我一遍还写不对的，考虑将每个串排成合法的最小字典序即可。

感觉好好构造不如随机化。记使根的度数不为 $1$，记叶子个数为 $lf$，首先观察到答案下界为 $\lceil \frac{lf}{2} \rceil$，考虑对着下界构造。

考虑对于一个节点，它子树内还未匹配的叶子至少有一个会被上传到父节点，并记录来源；否则考虑消除还未匹配的叶子，注意不能消除同一来源的叶子，否则不合法。

最后还不能匹配的直接到根即可，可以发现这样的点不超过 $1$ 个。

arc087f。

首先转化题意为：找到一个排列 $p$，使 $\sum dis(i,p_i)$ 最大。

考虑答案的上界，对于每条边左右两侧的两个连通块，记其大小分别为 $s_1,s_2$，那么这条边最多产生的贡献为 $2 \min(s_1,s_2)$，即子树内点都向外连。

考虑让重心作为根，定义一个点合法当且仅当 $(i,p_i)$ 不在根下同一子树内。问题转换为有多少个排列 $p$，能使所有点都合法。对于这个问题，我们套路的考虑容斥，令 $f_i$ 表示子树内至少有 $i$ 个点不合法的方案数，那么对于一个大小为 $x$ 的子树有 $f_i=(C_x^i)^2 i!$，背包合并得到整个树的 $f$，最后容斥计算答案即可。

首先根据后手的策略扫描线，按照 $b_i$ 从大到小排序。直接考虑贡献太麻烦，先假设所有牌都贡献了 $-b_i$，那么一张牌被取就会产生 $a_i+b_i$ 的贡献。

考虑记一张牌被取了为 $1$，否则为 $0$，那么一个合法状态应为：对于所有前缀，有前缀和 $\leq \lceil \frac{len}{2} \rceil$。

基础的贪心策略是，去找当前 $a_i+b_i$ 最大的位置，如果加上这个位置后所有前缀都合法，那就加入，可以发现这样一定不劣。

每次都暴力去扫太劣，考虑每一轮修改后会产生哪些影响：首先删去这个元素，如果它本身不计入答案则无影响，否则考虑将它从答案中剔除，找到剩余未选项中 $a_i+b_i$ 最大的位置，将它计入答案。

然后考虑加入新的元素，考虑先将它加入答案，然后找到第一个不合法的前缀，找到其中 $a_i+b_i$ 最小的位置将其删去，可以证明这样操作后所有前缀都合法且一定不劣。

以上过程均可以使用线段树上二分维护，时间复杂度 $\text{O}((n+m) \log n)$。