UNR 5 题解
提问系统
暴力 dp 前缀和优化可以做到 $n^5$ 或 $n^4$，再优化则必然要涉及到 $p_r p_b^2$ 的组合意义了：选 $1$ 个 R 和 $1$ 个 B
这不是「数树」的套路吗…… $dp[x, dr, db, 0/1, 0/1/2]$ 表示 $x$ 子树里，向下的链最大 R 个数为 $dr$，最大 B 个数为 $db$，选了几个 R，选了几个 B，$n^3$ 就是这么容易……
考虑优化：dr 和 db 意义改为 $x$ 到根的链（不包括 x）中 R 和 B 的个数，$dr + db = dep_x$ 就优化了一维。dp 的时候相当于递归到子树中算出「$x$ 以上预先占位占了 $dr$ 个 R」的方案数，再拼上 $x$ 贡献。
还是觉得很巧妙啊 owo
答案查重
神仙计数题？
两个子树映射过去相同，那么它们形态必然相同。
枚举一些「作为根，树互不同构」的点染 $1$，变成有根树，
$f_i(x)$ 表示 $i$ 子树关于染色点个数本质不同方案的 EGF
$f_u(x) = (1 + x) \prod\limits_{v} f_v(x) \prod ( \sum\limits_{i = 0}^k \frac{ (g(x) - 1)^i }{i!} )$
其中第一类是子树互不同构的儿子 $v$；第二类是假设有 $k$ 个儿子子树同构，其 $f(x)$ 都为 $g(x)$。若 $k$ 趋近于 $+\infty$, 贡献就是 $e^{g(x) - 1}$，所以贡献是 $\sum\limits_{i = 0}^k \frac{ (g(x) - 1)^i }{i!}$。直接 dp 就是树上背包合并的复杂度，单次 $O(n^2)$。
枚举根非常笨蛋，把重心当成根显然是正确的，因为对于原来的每一种方案，其中彼此同构的子树（显然 $size \leq n / 2$）在当前树中依然同构。这样你会了 $O(n^2)$
来来来我们优化。EGF，树——你想到了什么？「花朵」！
重链剖分。无同构兄弟的 $f$ 直接乘给链顶；同构子树呢——分治 FFT，两只 log 时间内给你跑出来！
现在你已经得到许多链上点的儿子的 EGF 堆在链顶，就等着全部卷起来算出链顶的答案 EGF
那么启发式卷积即可，堆维护。
三 只 log 1s 过 十 万
实现细节算少的（？）但 xml 都调傻了。
获奖名单
最低档暴力根本不是 $O(n! * 2^n)$ 啊…… $n!$ 确定顺序后从两边往中间确定，有单个直接 chk，否则…… 也是直接 chk。
考虑正解。显然有两种匹配（指在中轴两边的）：
- 相同的长度为 $2$ 的字符串彼此匹配
- 嵌在一起的（题解中称为「交替扩展」），例如第一个串为 [ab][cd]，第二个串为 [a][bc][d]
可以看作图上问题：$m + 1$ 个点，为 $1 ~ m + 1$，对于单个字符 $a$，连边 $(m + 1, a)$；对于字符串 $ab$，连边 $(a, b)$
有解条件：
$L$ 为偶数
两种 case：
- 两个相同串：$0$ 所在连通块存在欧拉回路，其他连通块（都是 $l = 2$ 的字符串）每条边出现偶数次。
- 中间有个 $aa$，两边两个相同串：存在一个边出现奇数次的自环
$L$ 为奇数
$0$ 所在连通块存在欧拉通路，并且一个端点是 $0$，其他连通块每条边出现偶数次
由于题目良凉心的保证有解，你只需根据判定过程构造即可。
为什么小清新构造题给 xml 写这么 shit（shit 代码可以在 uoj 提交记录里找到）：
- 善于运用 STL 让你没有烦恼，map yyds
- 邻接表建图，用奇偶表示方向。
诡异操作
naive 如你，以为记录区间 Or 和 sum，每次修改递归到叶节点就是两只 $log$ 了，然而它只能过两个特殊性质包！第一个 $3000$ 的包都过不了…… ——因为事实上每除一次都可以再做 $128$ 次 and，所以是 $O(n 128^2 logn)$
SGT 上每个节点最多被访问 $128$ 次，因此复杂度至少为 $O(128n)$
打标记下传就是 $O(n 128^2 + 128 qlogn)$
考虑优化这个标记下推的复杂度。（超妙啊…… 真就全场都被毒杀了，明哥 nb！）
每个节点维护一个长度 $128$ 的数组表示该区间在每一位为 $1$ 的个数。那么现在把每位展开，变成一个 $128 * log(len)$ 的矩阵。
我们由维护「每行 1 的个数」变为维护「每列的和」。注意每列的和依旧是一个 $2^{128}$ 以内的二进制数（方便直接与），因为左右儿子合并给父亲的时候进位是进给更高一级的列。不懂画图。
这样信息上传就是 $O(log(len))$ 的加法，打标记就是 $O(log(len))$ 每列做与。
锁定区间的复杂度为两只 $log$（除还是要递归到叶子结点做的，然后一路合并上来）
复杂度 $O(qlog^2n + \sum\limits_{i \in Node(SGT)} log(len_i) * 128 = qlog^2n + 128n)$
排名预测
要求构造一个排列 $b$，满足：
- 父亲小于儿子
- 每次可以交换一对父子当且仅当父亲比儿子小
- 通过若干次交换能够变为 $a$
这边把 b 当成 ddm 序了…… 应该没错吧……
假设已经确定了 $b$，如何构造交换顺序：从 $b$ 最小的叶子开始做，从它祖先中拉一个给它，并删掉这个叶子，更新 $b$，发现这样不会改变偏序关系，并可以转化为子问题。
有解情况：$\forall x, b_x < \max_{y \in Subtree(x)} ( b_y )$（注意这里的 b 是时刻更新的）
如何确定 $b$：$dp_x$ 表示 $b_x$ 至少得是多大。按照 dp 值遍历儿子更新 $dp_x$。最后检查 $dp_1$ 是否为 $1$。