【解题报告】联合省选 2022
$\text{preprocessor}$
注意到输出长度 $\le 1000$，我的实现方法是直接暴力递归展开，使用了 map<string, string>，看起来没有被卡（
$\text{tree}$
首先考虑暴力枚举一个端点，抓出上面的所有权值区间 $[l_i,r_i]$。
考虑枚举最小值 $x$，则所有元素都要在 $[x,x+K]$ 之间，把区间分为：
- $l_i< x\le r_i$
- $x\le l_i\le r_i\le x+K$
- $l_i\le x+K< r_i$
三类，贡献分别是：
- $r_i-x+1$
- $r_i-l_i+1$
- $(x+K)-l_i+1$
全部乘起来就是第一问的答案。但这样算出来是所有“最小值 $\ge x$，最大值 $\le x+K$” 的方案，如果枚举了最小值，就会算重。
解决方法是容斥。如果把上述过程的答案称作 $\text{calc}(x,K)$，容易发现 $\text{calc}(x,K)-\text{calc}(x+1,K-1)$ 就是最小值恰好是 $x$ 的，满足条件的方案数。只需对所有 $x$ 求和即可。
同时，注意到 $x$ 被链上的 $[l_i,r_i]$ 划分成 $\mathcal{O}(n)$ 段，其中每一段中，上述三类区间的分类完全一致。
一组“三类区间的分类”最后显然会导出一个 $\mathcal{O}(n)$ 次的多项式，只要能求出这个多项式的系数，那么只要自然数等幂和就能计算每个区间内的 $x$ 的答案和了。
本人在考场上并没想清如何维护多项式，于是考虑插值。
考虑对每一个多项式相同的值域区间，拿出值域上前 $\mathcal{O}(n)$ 个点就可以插出这个多项式。
如果直接 $\mathcal{O}(n^2)$ 枚举链，复杂度将会是 $\mathcal{O}(n^4)$，不过注意到可以通过换根 $\text{dp}$，点分治，或一个简单的直接对子树合并的做法，来在 $\mathcal{O}(n)$ 的时间里计算所有链的答案。看起来换根 dp 劣于后两个
得到点值之后直接拉格朗日插值插出系数，然后自然数等幂和是一种方法。不过我们注意到只要把点值进行前缀和，最后的答案就会变成前缀和后的多项式的两个单点的点值差，常数小得多。
至于第二问，通过上述类似的方式计算答案后容易发现他同样是一个 $\mathcal{O}(n)$ 次多项式，然后和第一问一样做。
时间复杂度 $\mathcal{O}(n^3)$。考场写了最慢的做法，最后只剩 60/ll
$\text{community}$
大抵参考 Itst 的题解/bx。
性质 $\text{AB}$
首先容易想到转化为一个图论模型：若有 A B louxia，则连边 $B\to A$。
每次一个连续段一定以学术消息开始，然后是若干的 louxia。这指引我们建立虚点 $S$，每出现一条 $A$ 的学术消息，就连边 $S\to A$。
由于 $\text{B}$ 性质指出所有边都可以被满足，且每个人都发过学术消息，所以我们尝试找出图的欧拉回路。计算每个点 $x$ 的入度 $\text{in}_x$ $-$ 出度 $\text{out}_x$，由于性质 $\text{B}$，必有 $\text{out}_x \le\text{in}_x$。只要向 $S$ 连边补齐出度即可。
性质 $\text{A}$
相比性质 $\text{AB}$ 只需最小化不满足的限制个数。
根据上述建图方式，唯一问题是可能 $\text{out}_x>\text{in}_x$。考虑 $x$ 的一条出边 $x\to y$。考虑放弃这条限制，则这条楼下消息的效果将等价于学术消息，相当于断边 $x\to y$，连边 $S\to y$。
该操作只将 $\text{out}_x-1$，容易得知这样构造是最优的。
性质 $\text{BC}$
出现楼上消息，但是 A B loushang 和 B A louxia 不同时出现。这意味着不可能在走了一步 $A\to B$ 后，满足的限制一次性增加了 $2$。
那么重新观察每一条满足条件的链，一定会形如：若干楼上消息 $+$ 一个学术消息 $+$ 若干楼下消息。
题解指出可以对楼上信息、楼下信息分开建图 $G,G'$，出现 A B loushang 则连边 $A\to B$，出现 A B louxia 则连边 $B'\to A'$。
最后一条满足条件的链会形如：在 $G$ 走一条链到 $A$，通过 $A$ 的学术消息跳转到 $G'$ 中的 $A'$，然后在 $G'$ 走一条链。
则当出现一条学术消息，只需要连边 $A\to A'$ 即可。
同样建立虚点 $S$，对于 $G$ 中的点，若 $\text{in}_x<\text{out}_x$ 则连边 $S\to x$；对于 $G'$ 中的点，若 $\text{out}_x<\text{in}_x$ 则连边 $x\to S$。
$\text{B}$ 性质告诉我们这样调整后，图存在欧拉回路。
性质 $\text{C}$
和性质 $\text{AB}$ 到性质 $\text{A}$ 一样，性质 $\text{BC}$ 到性质 $\text{C}$ 的问题在于，可能存在一些点使得 $S$ 无法纠正其度数。
此时我们同样考虑放弃尽量少的限制，使得 $G$ 中点满足 $\text{in}_x\le \text{out}_x$，$G'$ 中点满足 $\text{out}_x\le \text{in}_x$。
我们对 $G$ 中元素维护 $s_x=\text{in}_x-\text{out}_x$，$G'$ 中 $s_x=\text{out}_x-\text{in}_x$。我们的目标相当于使得任意 $s_x\le 0$。
放弃一条楼上消息 A B loushang，相当于断边 $A\to B$，加边 $A\to A'$。这意味着 $s_B\leftarrow s_B-1, s_{A'}\leftarrow s_{A'}-1$，这对 $B,A'$ 都有好处。放弃楼下消息，可以推出同理，也是对两个点都有好处。
那么这意味着，如果放弃某一条限制，涉及的两个 $s$ 均为正，那么他的贡献可以看作 $2$。涉及的只有一个 $s$ 为正，那么贡献为 $1$。本质上就是最大化贡献为 $2$ 的限制个数。
最大化贡献为 $2$ 的限制，又一条限制会使得 $G,G'$ 中各一个点的 $s$ 同时 $-1$，明显是一个二分图最大流。
剩下还不够的就只能通过贡献为 $1$ 的限制来补齐了。
$s_x\le 0$ 后，只需要按照性质 $\text{BC}$ 的做法用 $S$ 修正出入度即可。
无特殊限制
与性质 $\text{C}$ 的唯一不同在于：性质 $\text{C}$ 的每条链都形如：若干楼上消息 $+$ 一个学术消息 $+$ 若干楼下消息。
但出现 A B loushang，B A louxia 之后，可能会出现：若干楼上消息 $+A+B+$ 若干楼下消息，使得上述两条限制同时满足。
可以发现，同时满足两条限制在之前是从来没有出现过的，之前每次至多满足一条贡献。同时，可以说明将所有 A B loushang，B A louxia 的信息合并在一起，一定是最优的。
可以考虑调整，至多就是将两条链从之前的方案上割出来，然后再拼到一起，这样至多减少两条限制，又把两条限制加回来了，一定不劣。
于是，可以先把所有这样的 $(A,B)$ 找出来，将这两条边看作 $A\to B'$，然后运行性质 $\text{C}$。即可通过本题，由于需要二分图最大流，所以时间复杂度是 $\mathcal{O}(m\sqrt{n})$。
$\text{card}$
套路地把 $\sqrt{V}$ 以上和以下的质数分开考虑，一个数至多只有一个 $>\sqrt{V}$ 的质因子。$\sqrt{V}$ 以下的质数只有 $14$ 个，容易想到 $\text{FMT}$、指数级容斥的做法。
那只需要枚举给出的，小质数的子集，钦定他们不出现（同时满足所有 $>\sqrt{V}$ 的质数都出现），这可以直接预处理 $2^{14}$ 种小质数的子集中，在每一个大指数的集合中，有多少方案使得这些小质数不出现。
然后每次大力枚举给出的大质数，复杂度是 $\mathcal{O}(2^{14}\sum c)$，看起来可能被卡。可能存在某种方式把 $43$（最大的小质数）也看作大质数，常数除 $2$。不过我加了玄学优化，跑的挺快
$\text{bracket}$
从 $\text{WC2022 T1}$ 容易想到将括号序转变为树，左括号权值看作点的权值。
那么操作 $2$ 就是交换相邻的兄弟，操作 $1$ 大概做的是：把与 $p$ 相邻的兄弟 $q$ 变成 $p$ 的儿子，$q$ 的儿子也变成 $p$ 的儿子，花费 $x\times v_p+y\times v_q$。
最后的目标明显是变成一条链。那么“感性理解”我们总是先处理“还未变成链的，深度更浅的点”。也就是一层一层把点都推下去。
那么每次做的事情大概是：选择一个点 $p$，将这个点的兄弟通过某些方式，全部变成 $p$ 的儿子。然后这些点与 $p$ 本身的兄弟进入下一层操作。我们称将 $p$ “固定”。
Case 1: $x=0,y=1$
相当于只需要花费 $q$ 的权值。注意到权值越大的元素，我们越早把他固定在链上，他的贡献权值就越小。
容易给出这样一种方法：若当前权值最大的是 $p$，直接将所有其他兄弟连到 $p$ 上，这样不仅将 $p$ 固定了，同时是将元素下推所需要的代价下界。容易说明其正确性。
Case 2: $x=1,y=1$
还是希望把尽量大的尽早固定。但是如果仍然和上面一样每次都和最大的 $p$ 操作，可能代价很大。
注意到所需要的权值下界是 $s+t\times \text{mn}$，$s$ 是元素和，$t$ 是一个固定权值，$\text{mn}$ 是最小权值。这是将最小值固定的代价。
不过通过这种方式，也可以固定最大值。我们只需要将除了 $x$ 之外的元素先与 $\text{mn}$ 操作，然后把 $\text{mn}$ 接到 $x$ 下面即可。
Case 3: $x=1,y=0$
考场不会。此时的情况和上面不同，我们无法同时最小化代价，并“固定”最大权值的点。
不过，容易发现如果最后要固定 $p$，那么除了 $p$ 之外的点，一定首先和除 $p$ 之外的最小值 $\text{mn}$ 合并（代价全都是 $\text{mn}$），然后再花费 $v_p$ 将 $\text{mn}$ 下推。
我们尝试将贡献拆分，可以将贡献看作两类：
- 作为某一层的 $\text{mn}$，贡献系数是“元素个数 $-2$”。
- 作为某一层被固定的元素，贡献系数是 $1$。
第二种贡献只有最后一层没有。因此如果我们将 $p$ 留到最后，第二类的贡献和就是 $\text{sum}-v_p$。
考虑暴力，不妨直接枚举 $p$，那么一定不会在更上方固定 $p$。同时，每一层“元素个数 $-2$”的系数实际上是可以预先计算的，所以我们只需要使得每层的 $\text{mn}$ 尽量小即可。
于是，每次我们都选择固定除了 $p$ 之外的最大值，对所有 $p$ 的答案取 $\min$，即可做到 $\mathcal{O}(n^2\log n)$。事实上，上述过程删去任何除 $\text{mn}$ 和 $p$ 之外的元素都是一样的，他们终究会被删除且永远不会成为 $\text{mn}$ 了。
接下来的问题就是如何优化。如果 $p$ 还不确定，那么在某一层应该选择固定什么样的元素？
注意到我们总是希望固定“非最小值，非最大值”，感性理解：最小值可以贡献 $\text{mn}$，最大值可能留到最后作为 $p$。
这同样可以通过上面枚举 $p$ 的过程说明：当某一个时刻我们通过选择“非最大值，非最小值”，恰好固定了 $p$，那么此时我们将 $p$ 修改为当前的最大值，最后的答案一定不劣。
不过在一个情况下会出现问题：当前层只有两个元素。若当前的 $p$ 是较大的元素，那么我们不可避免的要固定 $\text{mn}$ 或者 $p$。
尝试观察什么时候会出现“当前层只有两个元素”的情况。每一层的元素个数序列 $\{s_n\}$ 应该在一个前缀单调不降，然后开始以 $-1$ 为“斜率”下降。那么 $s_i=2$ 的层应该是一段区间 $[L,R]$ 和第 $n-1$ 层（可能存在 $s_i$ 均为 $1$ 的特殊情况）。
在 $L$ 以前，每层都是没有选择余地的；在第 $n-1$ 层我们显然固定较小的元素。从 $R+1$ 的层，由于 $s_i\ge 3$，所以可以直接套用上述贪心策略。
问题就是在 $[L,R]$ 之间如何选择了。注意到如果我们在 $[L,R]$ 中选择保留元素 $w$，那么 $[L,R]$ 中其他元素全都会被固定，代价为 $\text{tot}-v_w$，剩下只需要让上述的贪心来决定即可。
试着找出较优的 $w$。如果我们希望 $w$ 留到最后，那么一定会下传最大的 $w$；否则，如果 $w$ 不留到最后，那么权值越小，就越可能成为后面的 $\text{mn}$。而且，由于容易发现在 $R+1$ 往后，候选元素中的 $\max$ 单调不降，$\min$ 单调不增，所以不会存在一个元素“先作为 $\min$，然后变为 $\max$ 保留到最后”。
于是，只需要找到 $[L,R]$ 中权值最大、最小的 $w$，进行两遍贪心即可。时间复杂度为 $\mathcal{O}(n\log n)$，可以通过一些简单的优化做到 $\mathcal{O}(n)$。
$\text{mis}$
做法 $1$：
$\text{sto lzh zxy orz}$。
首先容易看作每个点走了一条路径，贡献系数是路径长度。由于每个点至多只有两个儿子，因此启发我们对 $\mathcal{O}(1)$ 条边的断边顺序进行讨论。
当断掉 $(x,y)$ 的边（$x$ 是父亲），那么可以看作将 $d_x$ “传入” $y$ 子树，将 $d_y$ “传出” $y$ 子树。
我们尝试设计如下状态：$\text{dp}(x,y)$ 表示考虑 $x$ 的子树内，还完全没有被操作，此时“传入”了 $d_y$（即 $x$ 处权值是 $d_y$），断掉子树内所有边所需的最小代价。
在转移的时候，只需要考虑左右儿子的断边顺序，此处我们令 $\text{ls},\text{rs}$ 分别为左右儿子，并钦定 $(x,\text{ls})$ 先断。
那么 $d_y$ 将会传入 $\text{ls}$，从 $\text{ls}$ 传出的一个元素 $v$ 将会继续被传入 $\text{rs}$。$v$ 继续传入 $\text{rs}$，意味着可能还需要一个状态表示“考虑 $x$ 和 $x$ 的右子树，传入 $v$ 的最小代价”；从 $\text{ls}$ 传出一个元素 $v$，意味着可能需要状态表示“从 $x$ 的子树传出元素 $v$ 的最小代价”。
于是，设置状态 $\text{in}(x,y,0/1/2)$ 表示考虑 $x$ 及 $x$ 的左子树 / 右子树 / 整棵子树，还完全没进行操作，此时传入 $d_y$，所需要的最小代价。
$\text{out}(x,y,0/1/2)$ 表示考虑 $x$ 及 $x$ 的左子树 / 右子树 / 整棵子树，还完全没进行操作，传出 $d_y$ 所需要的最小代价。
对于 $\text{in}$ 的转移，在钦定 $\text{ls}$ 先断后，由于 $d_y$ 传入，某一个元素 $v$ 传出，但状态中并没有同时记录传入和传出，所以我们尝试继续对 $\text{ls}$ 和两个孩子，与 $(x,\text{ls})$ 三条边的断边顺序进行枚举。
这里巧妙的地方在于，如果 $\text{ls}$ 的左右儿子都存在，且 $d_y$ 进入其中一个，那么最后 $\text{ls}$ 传出的元素，一定来自另外一个儿子。这样就不再同时需要 “传入”和“传出”的信息了。
然后进行分类讨论，通过一些简单的优化即可做到 $\mathcal{O}(n^2)$。讨论情况数大概是 16 种
如果会了别的做法再来补