梅花侍从

idea, solution, std, data from GeZhiyuan

直接做肯定不好做，我们考虑分析一下结构。对于划分出来的两组，我们观测其在 $x$ 中的相对位置关系，分别用 X 和 O 表示两组内元素的位置，发现有意义的只有 XXOOOX 和 XXXOOO 两种。其他的可以进行如下替换：

XXOXOO -> XXXOOO
XXOOXO -> XXOOOX
XOXXOO -> XXOXOO -> XXXOOO
XOXOXO -> XXOOXO -> XXOOOX
XOXOOX -> XXOOOX
XOOXXO -> OXOXXO => XOXOOX -> XXOOOX
XOOXOX -> XOOXXO -> OXOXXO => XOXOOX -> XXOOOX
XOOOXX -> OXOOXX => XOXXOO -> XXOXOO -> XXXOOO

如上的每一次转变都显然严格不劣，至此我们分析出了所有可能的位置关系，实际上也正对应这前两组小样例的情况。由于可行的两种相对位置较为特殊，于是直接区间 dp 即可，记录 $f_{l, r}$ 表示 $x_l , x_{l+1}, \dots, x_r$ 划分的答案。复杂度 $O(n^3)$。

方片骑士

idea, solution, std, data from GeZhiyuan

小插曲

本题为我在验 Problem - 2006E - Codeforces 时看错题得到的产物，并在当时进行了查重，但由于跨度的时间过长，没想到在最近的一场 CF Div.2 中出现了此题的弱化版 Problem - 2031E - Codeforces。但是好在那题的做法虽然是正解的一部分，但也只能多通过 Sub2 获得 $15$ 分，并且作为萌萌的第二题本来也是希望能给大家送足够的分。但作为出题人的查重失误还是在此处给被影响到的所有人深深致歉。

算法 I

不难看出最终的树每个结点实际上都对应了原树的一个连通块。因此我们先假设定好根，然后进行如下动态规划：

• $f_u$ 表示 $u$ 这棵子树，以 $u$ 为根的树至少需要多大的满二叉树收缩得到，同样的大小为 $s$ 则记录 $\log_{2}{(s+1)}$ 的值。

直接合并即可，有：

• 如果 $u$ 只有一个儿子 $v$，则 $f_u = f_v + 1$。
• 否则令 $u$ 的儿子集合为 $S$，$f_u = \lceil \log_2 (\sum_{v \in S} 2^{f_v}) \rceil$

直接枚举根并进行动态规划，可以做到 $O(n^2)$，如果不拼链和菊花，预计得分 $30$。

算法 II

考虑进行换根，记录：

• $g_u$ 表示去除 $u$ 这棵子树，并以 $u$ 的父亲为根的树至少需要多大的满二叉树收缩得到，同样的大小为 $s$ 则记录 $\log_{2}{(s+1)}$ 的值。

考虑换根时动态维护 $\sum_{v \in S} 2^{f_v}$，相当于先将所有信息加入进去，然后每次查询如果删除一个的贡献是什么。

直接暴力找前驱后继可以做到 $O(n \sqrt n)$，预计得分 $50$ 至 $75$；也可以用线段树维护，复杂度 $O(n \log n)$，预计得分 $75$ 至 $100$。

也可以先将所有信息加入，然后记录二进制下的最高位，次高位，次次高位的位置，通过一系列分类讨论可以做到 $O(n)$。

算法 III

算法 II 实际上非常愚蠢，因为可以观察到，本题不需要询问每个根的答案，只需要知道所有根的最小值。

因此考虑换根时递归到 $u$ 时，对于所有 $u$ 的儿子 $v$，只有 $f_v$ 最大的才可能成为更优的根，其他的无需递归，因此这样暴力做就是 $O(n)$ 的，常数优秀的同时非常好写，预计得分 $100$。

算法 $\pi$

这题好像处理的方法非常多，欢迎大家在下方讨论。

可能有一些极快或者我没有料到的 $O(n \sqrt n)$ 也通过了此题。（真实性存疑）

还有高手

正如 小插曲中 所说，本题为我在验 Problem - 2006E - Codeforces 时看错题得到的产物。与那题相同，本题也可以支持像那题一样每次添加一个叶子并进行询问！但由于过于毒瘤还是选择了当下的版本。 你可以试试能解决 $n \leq 2 \times 10^5$ 并动态增加叶子的版本吗？

以下是来源于 huahua 的做法：

我们先把询问离线，把最终树的结构拿到，然后对树进行树剖，进行 ddp。

考虑 ddp 需要什么，我们对于每个结点 $u$，先对其所有轻儿子建立一棵线段树，维护轻儿子的 $\sum 2^{f_v}$ 在二进制下的值。

然后我们再考虑加入重儿子，对于没有轻儿子的显然好处理，否则假设重儿子的 dp 值为 $x$，而 $\sum 2^{f_v}$ 的最高位为 $a$，次高位为 $b$。

对于不存在 $b$ 的情况：

• 如果 $x > a$ 则 $f_u = x+1$。
• 否则如果 $x \leq a$ 则 $f_u = a+1$。

对于 $b = a - 1$ 的情况，我们令 $c$ 为最小的满足 $\sum 2^{f_v}$ 在二进制下第 $[c, a]$ 都为 $1$ 的非负整数：

• 如果 $c$ 不是最低位：
  • 如果 $x > a$ 则 $f_u = x+1$。
  • 如果 $c \leq x \leq a$ 则 $f_u = a+2$。
  • 如果 $x < c$ 则 $f_u = a + 1$。
• 如果 $c$ 是最低位：
  • 如果 $x > a$ 则 $f_u = x+1$。
  • 如果 $c < x \leq a$ 则 $f_u = a+2$。
  • 如果 $x \leq c$ 则 $f_u = a+1$。

对于 $b < a-1$ 的情况：

• 如果 $x > a$ 则 $f_u = x+1$。
• 如果 $x = a$ 则 $f_u = a+2$。
• 如果 $x < a$ 则 $f_u = a+1$。

不难发现在所有情况下，$f_u$ 始终是一个关于 $x$ 的至多三段的分段函数，始终为最后一段为 $x$ 上系数为 $1$ 的一次函数，且除最后一段外为常函数。

然后我们再次观察这个转移的特点，我们尝试观察对于一段重链，令链首为 $t$，而我们在链末传入的 $x$ 和最终 $f_t$ 是什么关系呢？实际上仍然是满足如上条件的至多三段分段函数！

于是我们就解决了非换根的问题，对于每条重链我们也建立一棵线段树去维护函数的复合，总复 $O(n \log^2 n)$。利用全局平衡二叉树的技巧可以做到 $O(n \log n)$。

对于换根的问题实际上是简单的，这种 ddp 本身也支持换根，且不难发现在加入叶子的过程中，最优的根只有两种可能，不动或者沿着原根到新加入的叶子的路径移动 $1$ 步。至此我们在 $O(n \log n)$ 或 $O(n \log^2 n)$ 内解决了该问题。

红桃王后

idea, solution, std, data from xianhz

子任务 I

我会暴力枚举/分类讨论！

直接枚举每轮是哪些人获胜，或者直接把 $n\leq 3$ 的情况画出来逐一判断，这些都是可行的。

总之只要是正确的做法大概都能通过这档部分分。

子任务 II

我会观察性质！

考虑建图 $G$， 对于所有关系 $u$ 战胜 $v$ 连一条有向边 $u\to v$。

注意到对于一个合法的图，必要条件有：

• 是个 DAG。（若 $u$ 战胜 $v$ 则 $u$ 的排名会严格比 $v$ 高）
• 有恰好一个点没有入边只有出边。（即第一名是全胜的）
  • 实际上易发现有 $i$ 条入边的有恰好 $\binom ni$个人。
• 第一名直接或间接战胜了所有人，其中 $u$ 直接或间接战胜 $v$ 可以理解为图中存在一条从 $u$ 到 $v$ 的路径。

所以对于每一轮的败者，在他们在败者组中决出的第一名（设为 $A$ ）在原图中恰有一条入边，且一 个人在败者组当且仅当它在 $A$ 的可达集合中。

所以对于每一轮不再枚举哪些人获胜，而是只在恰有一条入边的点中枚举 $A$ 即可。复杂度 $O(n!2^n)$。

子任务 III

我会对暴力记忆化！

在刚才搜索的过程中加上记忆化，即维护 $f_S$ 表示如果集合 $S$ 内的人参加比赛是否存在合法方案。

这看上去作用有限，甚至是个负优化，但你如果把它加上就会发现自己莫名其妙通过了这个子任务。

你可能会质疑出题人的数据强度。（好吧可能确实需要质疑）但这个做法的复杂度其实是有保证的。

子任务 IV

我知道记忆化为什么是对的！

考虑再建反图 $G_r$，对于所有关系 $u$ 战胜 $v$ 连一条有向边 $v\to u$，由对称性它也满足我们之前推的所有性质。

考虑去分析状态数：注意到对于一个 $f_S=1$ 的 $S$，它一定由 $S$ 中的第一名在 $G$ 中的可达集合 与 $S$ 中的最后一名在 $G_r$ 中的可达集合 的交生成。

说人话一点就是：如果你知道了 $S$ 中的第一名和最后一名你就可以唯一确定 $S$ 了，所以合法的 $S$ 的数量是不超过 $O(2^{2n})$ 的，这也是对刚才记忆化的复杂度的证明。

所以你去拿 $dp_{i,j}$ 表示：由 $i$ 和 $j$ 生成的 $S$ 在 $G$ 中的导出子图是否合法。

让我们再分析一下状态数。

最坏情况是：第 $i$ 个人直接或间接战胜了所有 $i\subset j$ 的 $j$，直接或间接输给了所有 $j\subset i$ 的 $j$。（这里将 $i$ 视作的集合就是 0-index 时 $i$ 在二进制下的表出）

这时我们会搜索到一个元素当且仅当 $f_S=1$。而合法的 $S$ 能由一对 $i\subset j$ 的 $(i,j)$ 生成，而对于一对 $(i,j)$ 的转移复杂度应该是 $O(2^{|j\setminus i|}n^2)$

通过组合意义可证明复杂度是 $O(4^nn^2)$，这也给出了该题计数版本的一个多项式级别做法。

当然如果你对于子任务 3 的记忆化直接使用 xor hashing 存储状态，应该也可以通过该子任务，但代价呢？（upd：好吧因为是 IOI 赛制所以没法有什么代价）

子任务 V

我会猜结论！ 虽然上面的做法看上去很妙，但只用上述性质的话恐怕没法优化复杂度了。$3^n$ 级别的状态数让我们不得不借助题目本身的性质来优化 dp。

注意到若 $(i,j)$ 能被合法划分成 $(i,k_1),(l_1,j)$ 和 $(i,k_2),(l_2,j)$，则 $dp_{i,k_1}=dp_{l_1,j}=1$ 时必有 $dp_{i,k_2}=dp_{l_2,j}=1$，此时有 $dp_{i,j}=1$（这里合法划分的意思是两个集合间的边是一组完美匹配）

证明是容易的：考虑两个划分分别是 $A\oplus B,C\oplus D$ 和 $A\oplus C,B\oplus D$。

由更低阶的结论我们有 $f_A=f_B=f_C=f_D=1$，然后交换一下划分的顺序即可。

所以结论就是：我们只要能找到一组 $(i,k),(l,j)$ 使得这个划分在当前层没有矛盾，就可以往下递归，因为 $(i,k)$ 和 $(l,j)$ 一定都有合法解。

感性来说，就是我们不停划分会让每个子问题内部的限制更宽松，并且不会让一个之前原本可以使用的匹配变得不合法。（或者说就是无后效性）

所以我们直接枚举第 $2^{n-1}+1$ 名，去看它的可达集合和这个集合的补集之间的边是否是一组完美匹配即可判断。

复杂度 $F(n)=2^nn^2+2F(n-1)=O(2^nn^3)$。

子任务 VI

我会用位运算并行求可达集合与判断完美匹配！

考虑求可达集合无非是在一个有向图中，按一个边的顺序遍历，对于一条边 $(i,j)$，令 vis[j]|=vis[i]。

那么如果我们要求 个点的可达集合，就可以用位运算加速这个过程：对于第 $i$ 个点 $p_i$，初始令 $vis_{p_i}=2^i$，然后执行上述算法。

对于判断完美匹配方法也是类似的：对于一条边 $(i,j)$，令 d[i]+=vis[j]&~vis[i]， d[j]+=vis[j]&~vis[i]，最后判断是否所有 $d$ 都是 $1$ 。 由于我们只在乎 $d$ 是 $0$，$1$ ，还是 $\geq 2$ ，所以用两个值维护 $d_i$ 在第 $j$ 位是否 $\geq 1$ 和是否 $\geq 2$ 即可。

这样我们就将构造和计数复杂度分别优化成了 $O(2^nn^2)$ 和 $O(4^nn)$，足以通过本题。

黑桃国王

idea from wzc_IOI_czw, fast_photon, bunH2O; solution from zhoukangyang, Rainbow_sjy; std, data from Melania

准备工作

• 如果一条有向边 $u\to v$ 不出现在任何一个回路中（两个端点处在不同的强连通分量），可以直接删去这条边。
• 如果一个结点 $u$ 不出现在任何一个回路中（处在单独一个结点的强连通分量并且没有自环），可以直接删去这个结点。

删去这些东西以后，从任何一个结点 $u$ 出发，无论前面怎么走后面一定能走回去。也就是说：对于回路的一个可空的前缀 $u_0\to u_1\to\cdots\to u_i(i\geq0)$，一定能找到一个非空的后续 $u_i\to u_{i+1}\to\cdots\to u_ℓ(ℓ\geq i+1)$，使得 $u_ℓ=u_0$。

最小无穷路径

定义 $s(u,i)$ 表示从 $u$ 开始游走 $i-1$ 步形成的字符串里面字典序最小的那个。

定义 $f(u,i)$ 表示 $s(u,i)$ 在 $s(u,1)\sim s(u,n)$​ 里面去重之后的排名。

根据定义 $s(u,i)=a_u+\min\limits_{u\to v}s(v,i-1)$。

因此我们可以递推 $f(u,i)$ 等于二元组 $\left(a_u,\min\limits_{u\to v}f(v,i-1)\right)$ 在所有 $n$ 个（第 $i$ 步的）二元组里面去重之后的排名。

如果递推到了某个 $i$ 我们发现所有 $f(u,i)=f(u,i-1)$，那么 $f(u,+\infty)=\cdots=f(u,i+1)=f(u,i)=f(u,i-1)$。

注意到 $f(u,i)$ 不同的两个 $u$ 后面永远不会合并，而相同的两个 $u$ 后面有可能会分开。因此这个 $i\leq n$。

我们把 $s(u,+\infty)$ 称作 $u$ 的最小无穷路径。上面的算法可以在 $O(mn)$ 的时间内求出所有最小无穷路径。

性质 I

考虑刻画所有 $n$ 个最小无穷路径形成的结构。

假设最后有 $m$ 个不同的最小无穷路径（即 $f(1,+\infty)\sim f(n,+\infty)$ 的值域是 $1\sim m$）。

那么可以建出一个有 $m$ 个结点的根向环套树森林，每个结点上面写有一个字符，同时有唯一的一条出边指向另外一个结点。对于原图中的某个结点 $u$，森林中的结点 $f(u,+\infty)$ 的唯一出边指向的就是 $\min\limits_{u\to v}f(v,+\infty)$。

在这个根向环套树森林当中，（去重之后的）排名为 $i$ 的最小无穷路径等于从结点 $i$​ 出发沿着出边一直游走形成的无穷字符串。

由于所有 $m$ 个无穷字符串是两两不同的，我们的根向环套树森林一定满足以下两个性质：

1. 每个环 $C$ 一定不存在非整串的非空周期。
2. 每个结点 $u$ 的所有入度 $v_i$，上面写有的字符一定两两不同。

算法 I

固定一个起点 $u$，考虑所有 $u_0=u_ℓ=u$ 的回路生成的无穷字符串构成的集合 $S_u$。

• 如果最小无穷路径是一个纯循环 $o$ 形（意味着 $f(u,+\infty)=C^\infty$），那么 $S_u$ 有一个 最小值 $C^\infty$​：

  1. 如果 $S_u$ 里面包含唯一一个元素，那么 $C^\infty$ 可以属于序列 $s_1\sim s_k$；

  2. 只要 $S_u$ 里面包含至少两个元素，那么 $C^\infty$ 可以属于序列 $s_1\sim s_k$，但是序列 $s_1\sim s_k$ 里面不能包含任何 $>C^\infty$ 的字符串 $X$。

     （这是因为对于任何一个字符串 $X>C^\infty$，一定存在一个 $Y\in S_u$ 满足 $X>Y>C^\infty$。）

• 如果最小无穷路径是一个混循环 $\rho$ 形（意味着 $f(u,+\infty)=A+C^\infty$），那么 $S_u$ 有一个 不在 $S_u$ 中的下确界 $A+C^\infty$：

  1. 此时 $S_u$ 里面包含至少两个元素，当然序列 $s_1\sim s_k$ 里面不能包含任何 $>A+C^\infty$ 的字符串 $X$。

     （这是因为对于任何一个字符串 $X>A+C^\infty$，一定存在一个 $Y\in S_u$ 满足 $X>Y>A+C^\infty$。）

对于上述三种情况，我们分别把 $u$ 称作一个第零类／第一类／第二类结点。

最后我们计算答案。我们依次枚举 $i\in\{1,2,\cdots,m\}$，考虑 $f(u,+\infty)=i$ 的所有结点 $u$：

• 只要其中存在第二类结点，那么确定答案 $=i-1$，跳出循环；
• 否则如果存在第一类结点，那么确定答案 $=i$，跳出循环；
• 否则如果全部都是第零类结点，那么继续循环。

这里有一个小问题：我们已知一个结点 $u$ 的最小无穷路径是一个纯循环 $o$ 形，怎么判断它是一个第零类结点还是一个第一类结点？

我们考虑 $u$ 所在的强连通分量。只要这个强连通分量内存在一个生成不同字符串的回路，那么所有 $o$ 形都是第一类结点。

对于每一个强连通分量，我们刻画这个条件：拿出这些结点对应的无穷字符串排名。如果它们形成单独一个环，并且整个强连通分量内的任何一个结点 $u$ 所有出边 $u\to v$ 满足 $f(v,+\infty)$ 全部相同，那么所有 $o$ 形都是第零类结点；否则所有 $o$ 形都是第一类结点。

算法 I 的时间复杂度为 $O(mn)$，可以获得至少 $39$ 分。

算法 II

直接把算法 I 中计算 $f(1,+\infty)\sim f(n,+\infty)$ 的过程换成启发式分裂即可。

算法 II 的时间复杂度为 $O(m\log n)$，可以获得 $100$ 分。