贪心/构造/DP 杂题选做Ⅱ

由于换了台电脑，而我的贪心 & 构造能力依然很拉跨，所以决定再开一个坑（

前传：

贪心/构造/DP 杂题选做

u1s1 我预感还有Ⅲ（欸，这不是我在多项式Ⅱ中说过的原话吗）

24. P5912 [POI2004]JAS

一开始直接莽了个点分治，当我测过了样例美滋滋地一交，发现自己获得了 20 分的好成绩之后，才发现事情有那么亿点点不对劲（

不难发现，题目等价于求高度最小的点分树的高度，直接求有点困难，我们不妨来对其进行一些转化：我们考虑给每个点一个标号，那么问题可以转化为，求使得任意两个标号相同的点之间必须有一个点标号比它大，求最大标号的最小值。

考虑 DFS，DFS 到一个节点 \(x\) 时我们考虑贪心地给它赋上一个最小的标号，那么要求这个标号满足：

对于所有子树内与该点标号相同的点 \(y\)，\(x\) 与 \(y\) 之间至少有一个点编号比它大。
对于 \(x\) 不同子树内的两点 \(y,z\)，如果 \(y,z\) 标号相同并且 \(y,z\) 路径上不存在标号比 \(y\) 的标号大的点，那么 \(x\) 的标号比这样的点 \(y\) 的标号都要大。

注意到点分树高度肯定是 \(\log n\) 级别的，因此直接模拟即可。每次用个 mask 记录下所有满足存在一个点 \(y\) 标号为 \(p\)，且 \(y\to x\) 路径上的点的标号都 \(\ge p\) 的 \(p\) 的集合 \(S_1\)，再记录下所有满足存在两点 \(y,z\) 属于 \(x\) 的不同子树，它们的标号都为 \(p\)，且 \(y\to z\) 路径上不存在标号 \(\ge p\) 的 \(p\) 的集合 \(S_2\)，然后贪心地取 \(>S_2\) 中最大元素，且不在 \(S_1\) 中地元素作为 \(x\) 的标号。

时间复杂度 \(\Theta(n\log n)\)。

25. P3545 [POI2012]HUR-Warehouse Store

大概是模拟费用流板板题？

看到这种按时间轴进行的操作，我们通常可以按照事情发展的顺序进行贪心/反悔贪心。我们不难想到这样一个很 naive 的贪心：从前往后考虑所有操作，每次令答案加上 \(a_i\)，如果能付得起 \(b_i\) 件商品那就满足这个顾客的需求，不过这样贪心显然是错误的，因此我们考虑魔改它，也就是采用反悔贪心的思想。我们再用个堆维护目前被满足需求的顾客的 \(b_i\)，每次取出最大的这样的 \(b_i\)，我们不妨设之为 \(b_j\)，那么如果 \(b_j>b_i\)，并且去掉 \(b_j\) 以后剩余的库存能够满足 \(i\) 的需求，那么我们就不满足 \(j\) 的需求，改满足 \(i\) 的需求，根据费用流的思想可知该算法的正确性。

时间复杂度 \(\Theta(n\log n)\)。

26. P2587 [ZJOI2008]泡泡堂

不难发现最大值与最小值情况类似，因此下面只讨论最大值的情况，最小值的情况简单镜像一下即可。

考虑将浙江队所有选手的实力从大到小排序，然后我们贪心地先让尽可能多的浙江选手得 \(2\) 分，具体来说，我们按照实力顺序从大到小遍历每个浙江选手，然后在敌方选手的 multiset 中 lower_bound 一下找到小于该浙江选手且实力最高的敌方选手，然后将其从 multiset 中删除。

匹配完得分为 \(2\) 的浙江选手后，我们考虑尽量让剩余的浙江选手得分为 \(1\)，这部分就比较简单了，直接贪心令同分的浙江选手与地方选手匹配，使用 map 维护即可。

时间复杂度 \(\Theta(n\log n)\)。

27. P3620 [APIO/CTSC 2007] 数据备份

其实感觉类似的反悔机制还是挺喜闻乐见的罢（

考虑用个 set 维护相邻两个未被选择的办公楼及它们之间的距离，然后每次取出距离最小的相邻办公楼，不妨设之为 \(l,r\)，那么根据我们贪心的策略，此时 \(l+1\sim r-1\) 肯定按照 \(l+1,l+2\)，\(l+3,l+4\)，\(\cdots\)，\(r-2,r-1\) 的方式配对的，而加入 \(l,r\) 之后我们肯定按照 \(l,l+1\)，\(\cdots\)，\(r-1,r\) 的方式配对，直接减去 \([l+1,r-1]\) 的贡献加上 \([l,r]\) 的贡献即可。

时间复杂度 \(n\log n\)。

28. CF884F Anti-Palindromize

怎么……现在费用流都能混到我的这个 blog 里了呢（

考虑建立三排节点，第一排节点包含每种字符，即我们先对每种字符新建一个节点 \(x\)，并连一条 \(S\to x\)，容量为 \(c_x\)，费用为 \(0\) 的边，其中 \(c_x\) 为 \(x\) 在 \(s\) 中的出现次数。第二排节点包含所有二元组 \((p,c)\)，对于第一排的所有节点 \(c\)，我们都连一条其到 \((p,c)\)，容量为 \(2\) 的边，其中 \(p\in[1,n]\)。第三排包含所有原字符串中的位置，对每个二元组 \((p,c)\)，如果 \(s_p=c\) 则连一条 \((p,c)\to p\)，容量为 \(1\)，费用为 \(b_p\) 的边，同理如果 \(s_{n+1-p}=c\) 则连一条 \((p,c)\to n-p+1\)，容量为 \(1\)，费用为 \(b_{n+1-p}\) 的边，最后再从第三排所有节点向汇点 \(T\) 连容量为 \(1\) 费用为 \(0\) 的边，跑最大费用最大流即可。

时间复杂度 \(O(\texttt{能过})\)

29. P3045 [USACO12FEB]Cow Coupons G

一开始感觉这题和远古时期做的 CF436E 很像，然后就一直往那道题的方向想，结果没想出来，心态爆炸/dk

首先考虑一个非常浅显易懂的性质：如果前足够买得下折扣价最低的 \(k\) 头奶牛，那么这 \(k\) 头奶牛肯定都会至少以折扣价被买走，否则我们肯定可以调整策略使答案更优。

因此这样我们首先将所有奶牛按它们的折扣价排序，并令答案减去折扣价最便宜 \(k\) 头的奶牛的价格之和，如果某一次减掉某头奶牛的折扣之后，总价格被减到了 \(0\) 以下，那么就直接输出当前已有的奶牛个数。

然后考虑如何使用剩余的前买下更多的奶牛。不难发现，如果我们多买下了一头奶牛，那么只有两种可能，一是以原价买下，代价就是 \(p_i\)，二是以折扣价买下，但是由于我们总共只有 \(k\) 张折扣券，因此代价不能简简单单地视作 \(c_i\)，而要先将某个使用了折扣券的奶牛改为原价购买，再对该奶牛使用折扣券，代价为 \(c_i+\min\limits_{x\text{使用了折扣券}}p_x-c_x\)，不难发现这两部分都可以使用堆维护，具体来说，我们建立三个堆 \(q_1,q_2,q_3\)，其中 \(q_1\) 存储现在啥也没买的那些牛的 \(p_i\)，\(q_2\) 存储现在啥也没买的那些牛的 \(c_i\)，\(q_3\) 存储现在以折扣价购买了的那些牛的 \(p_i-c_i\)，这样两种情况代价的较小者可在 \(\Theta(1)\) 的时间内求出，总复杂度 \(\Theta(n\log n)\)。

30. CF1500C Matrix Sorting

一道非常妙的拓扑排序好题，能出出这道题的人怕不是神仙/bx

首先我们考虑求出矩形 \(A\) 中的每一行在进行这些操作后会对应到矩形 \(B\) 中的哪一行——显然如果矩形 \(A\) 中每行都不相同，那直接相同的行配对即可，如果矩形 \(A\) 出现了相同的行，那显然它们的相对位置顺序是不会改变的，直接按照它们在原矩阵中的顺序编号即可。这样我们可以新增一个 \(m+1\) 列，\(A\) 矩形第 \(i\) 行第 \(m+1\) 列的元素就是 \(i\)，而 \(B\) 矩形第 \(i\) 行第 \(m+1\) 列的元素则是 \(B\) 矩形第 \(i\) 行在 \(A\) 矩形中对应的行的编号。当然如果无法对应我们就直接输出 NO。

接下来考虑如何求出操作序列，我们倒着考虑操作序列，那么可以发现，我们最后一步可能操作的列，在 \(B\) 矩形中都是单调不降的，也就是说对于任意相邻两行 \(i,i+1\)，必须要有 \(b_{i,j}\le b_{i+1,j}\) 后，最后一次才有可能操作第 \(j\) 列，考虑完了最后一次操作，再考虑倒数第二次操作的列有什么限制，还是必须单调不降吗？非也，不难发现，加入最后一次操作的列为 \(x\)，倒数第二次操作的列为 \(y\)，那么如果 \(b_{i,y}>b_{i+1,y}\) 但 \(b_{i,x}<b_{i+1,x}\)，这种情况还是有可能合法的，因为虽然排 \(y\) 之后会导致 \(i,i+1\) 顺序颠倒，但是下一次排序我们又把它搬回来了，因此这种情况是不影响的，但是如果出现 \(b_{i,y}>b_{i+1,y}\) 且 \(b_{i,x}=b_{i+1,x}\) 就 GG 了，因为我们的排序是 stable 的，你前一次把 \(i,i+1\) 的顺序搞反了，后一次两行的关键字相同，它们的顺序还是反的。

那么我们应该从什么角度思考这个过程呢？不难发现，我们倒着考虑每一次操作 \(x\)，那么我们考虑完 \(x\) 之后，相当于把所有 \(a_{i,x}\ne a_{i+1,x}\) 的 \((i,i+1)\) 都“解锁了”，而如果考虑到某一步操作时，第 \(y\) 列存在一个 \(i\) 使得 \(a_{i,y}>a_{i+1,y}\)，且 \((i,i+1)\) 没有被“解锁”，那么上一步操作的就不可能是 \(y\)，因此我们可以考虑拓扑排序的过程，将相邻两行和每一列看作一个点，对于每对 \((a_{i,x},a_{i+1,x})\)，如果 \(a_{i,x}<a_{i+1,x}\)，那么我们连一条第 \(x\) 列向第 \(i\) 行的边，表示操作完第 \(x\) 列后 \((i,i+1)\) 就被解锁了，如果 \(a_{i,x}>a_{i+1,x}\)，那么我们连一条第 \(i\) 行指向第 \(x\) 列的边，表示第 \(i\) 行被解锁，是第 \(x\) 列能够被操作的必要条件，然后跑一遍类似拓扑排序的东西即可。只不过这里与一般的拓扑排序不同的一点是，如果一个点对应的是某一行表示的点，那么只要连向它的点中至少一个被选择，那它就可以设为被访问。

那么怎样统计答案呢？不难发现，初始局面相当于我们强制对 \(m+1\) 行排了个序，因此我们只需检验 \(m+1\) 列对应的点是否被访问即可，如果被访问了则倒着输出拓扑序列，否则输出 NO。

时间复杂度 \(\Theta(nm)\)。

31. CF280D k-Maximum Subsequence Sum

一开始看到题面，\(q\) 次询问？求 \(k\) 个不交区间的和的最大值？还带修？什么毒瘤，后来才发现我忽略了 \(k\le 20\) 的条件……无语了（

看到这个 \(k\le 20\) 我们可以很自然地联想到 NOI2011 超级钢琴 那道题，也进而可以设计出一个大致地框架：我们先将整个区间放到一个优先队列中，然后每次贪心地多选一个区间，取价值最大的选择方式，如此重复 \(k\) 步。

那么如何实现这个程序呢？一个非常 naive 的想法是，我们将当前没有被选择的区间放入一个优先队列，每次取所有这样的区间中，最大子段和最大的区间，然后将这段区间中和最大的 subarray 设为被选择，然后将旁边两个子段插入优先队列，但是这样显然是错误的，样例都过不去，因为样例恰好选择了整个数组，而按照上述算法，扩展完一步以后就不会继续扩展了，这就导致 \(k=1\) 与 \(k=2\) 答案相同。那么有什么补救方法呢？考虑反悔贪心。具体来说，我们增加一种扩展区间的方法：扣掉某个已经选择的区间的最小子段和，这个同样可以用堆维护。注意如果新增的价值 \(<0\) 就直接 break 掉。

时间复杂度 \(\Theta((n+q)\log n+Bk\log n)\)，其中 \(B=10^4\) 表示操作次数。

32. CF1373G Pawns

首先我们假设第 \(i\) 个棋子最终摆在第 \(k\) 行第 \(p_i\) 列，那么显然一组 \(\{p_i\}\) 符合要求的必要条件是 \(p_i\) 互不相同，且 \(p_i\ge y_i+|x_i-k|\)。

同时不难证明这也是充分条件，具体构造就是从 \(y_i\) 大的开始依次归位。

这样一来问题就变得很容易了，用个线段树维护 \(cnt_i\) 表示有多少个 \(y_j+|x_j-k|\ge i\)，那么答案就是 \(\max cnt_i+i-1\)，这个用线段树维护即可。

时间复杂度 \(q\log m\)。

33. CF1428G2 Lucky Numbers (Hard Version)

首先这题虽然有个多组询问，但每次询问都是一个数并且都不大，所以我们肯定会提前把所有 \(x\) 的答案都预处理出来然后 \(\mathcal O(1)\) 处理每个询问。

那么如何预处理每个 \(x\) 的答案呢？首先我们考虑一个不太对的多重背包做法：不难发现每一位的贡献可以拆开来统计，因此考虑对于每一位，我们统计拆出来的 \(k\) 个数中，这一位上所有数字的和。我们设 \(10^d\) 位拆出的所有数各位数字和为 \(s_d\)，那么我们肯定希望 \(s_d\) 尽量是 \(3\) 的倍数，而如果 \(s_d=3t\)，那么这一位的贡献都是 \(t·f_d\)，这个可以考虑建 \(3k\) 个体积为 \(3·10^d\)，价值为 \(f_d\) 的物品然后跑多重背包。

但是这样显然无法正确处理 \(x\) 不是 \(3\) 的倍数的情况。怎么办呢？考虑一个非常显然的性质：对于每一位，拆出的 \(k\) 个数中，最多只有一个数这一位上的数不是 \(3\) 的倍数，否则我们肯定可以调整，譬如 \(4+7\) 可以调整成 \(2+9\)。而且我们如果把那些不是 \(3\) 的倍数的位都放到一位上，肯定是不影响答案的，因此我们考虑枚举包含不是 \(3\) 的倍数的位对应的数是什么，设为 \(x\)，计算出 \(x\) 的价值，然后把 \(dp_x\) 的初值设为 \(x\) 的价值，然后再跑多重背包即可，注意此时每种物品的个数应为 \(3(k-1)\)。

为什么只讲 G2 呢？因为 G1 被我用暴力 \((10^6)^2·6\) 的数位 dp 艹过去了就没啥好说的了（

34. CF1452F Divide Powers

一道非常妙的贪心好题，给出题人点个赞/qiang

首先特判掉 \(-1\) 的情况，显然如果 \(\sum\limits_{i=0}^{n-1}cnt_i2^i<k\) 答案就是 \(-1\)。

考虑多出一个 \(\le 2^x\) 可能是哪些情况造成的，不难发现无非就三种情况：

某个 \(\le 2^x\) 经过了若干次拆分分成了一些更小的幂，那么显然每进行一次操作就会多出一个 \(\le 2^x\) 的幂，因此 \(t\) 次操作后会多出 \(t\) 个 \(\le 2^x\) 的幂。
某个 \(>2^x\) 的幂 \(2^y\) 经过若干次拆分完全变成了 \(\le 2^x\) 的幂，不难发现这部分会恰好经过 \(2^{y-x}-1\) 次操作将 \(2^y\) 变成 \(2^{y-x}\) 个 \(2^x\)。后面部分则可以归约到 1 操作。
某个 \(>2^x\) 的幂经过若干次操作部分分解为 \(\le 2^x\) 的幂，譬如 \(x=2\)，那么可将 \(2^4\) 拆分成 \(2^3+2^2+2^2\)。

对于这类贪心问题，我们不妨从性价比的考虑这三个操作。可以发现，\(1\) 操作性价比 \(=1\)，\(2\) 操作性价比 \(>1\)，而 \(3\) 操作性价比肯定不超过 \(1\)，因此我们肯定贪心地选择尽可能多地进行 \(2\) 操作。我们考虑从小到大遍历每个 \(>2^x\) 的幂，先尽量用 \(2\) 操作将其拆成 \(\le 2^x\) 的幂，如果我们发现拆一个 \(>2^x\) 的幂时，能够补完全部 \(\le 2^x\) 的幂，那么我们此时再使用 \(2\) 操作就不一定是最优的，我们就考虑拆这个幂，不妨设之为 \(2^y\)，那么我们考虑用 \(3\) 操作拆这个幂，同时记录下如果我们使用 \(1\) 操作，最多可以拆出多少个 \(1\)，然后边拆边更新答案即可。

时间复杂度 \(\Theta(qn)\)。

35. CF232C Doe Graphs

代码 10 分钟，debug 两小时

又是精神崩溃的一天/dk

首先这个 Doe 图是递归构造的，因此我们也可以尝试考虑递归地求解某些量，进而计算出答案，可以发现，在一个 \(n\) 阶 Doe 图中，有两个点是非常特殊的：\(1\) 和 \(|D_n|\)，因为只有经过它们才能进入其他 Doe 图，因此我们考虑设 \(F(n,x)\) 表示在一个 \(n\) 阶 Doe 图中，\(x\) 到 \(1\) 的最短距离，再设 \(G(n,x)\) 表示在一个 \(n\) 阶 Doe 图中，\(x\) 到 \(|D_n|\) 的最短距离，考虑如何递归地求解 \(F,G\)：

如果 \(x\le\text{fib}_{n-1}\)，则意味着 \(x\) 在左半边的 \(D_{n-1}\) 子图中，那么 \(x\) 到 \(1\) 有两种可能，要么直接在左半边的子图内走到 \(1\)，要么先走到 \(|D_{n-1}|\)，再走到 \(|D_{n-1}|+1\)，最后再走到 \(1\)，注意，后面那种情况很容易忽略，我因为忽略了后者而疯狂 WA 14。\(x\) 到 \(|D_{n}|\) 则只能要么先走到 \(1\)，要么先走到 \(|D_{n-1}|\)，再走到 \(|D_{n-1}|+1\)，再在右边的子图内走到 \(D_{n}\)，而打个表可以发现，在 \(D_n\) 中，\(1\) 与 \(|D_n|\) 的最短距离为 \(\lceil\dfrac{n}{2}\rceil\)，因此在右边子图中经过的最短距离就是 \(\lceil\dfrac{n-2}{2}\rceil\)。
如果 \(x>\text{fib}_{n-1}\)，那么 \(x\) 到 \(1\) 肯定会先在右边子图内走到 \(|D_{n-1}|+1\)，再一步走到 \(1\)，而 \(x\) 到 \(|D_n|\) 则只能在右半部分走，到左半部分肯定是不优的，这个同样可以递归求出。

这样单次求解 \(F/G\) 的复杂度就降到了 \(\Theta(\log n)\)，接下来考虑如何求解答案，我们设 \(H(n,a,b,len)\) 表示在 \(n\) 阶 Doe 图中，\(1\) 与 \(D_n\) 之间连了一条长度为 \(len\) 的链（注意，这种情况同样也很容易忽略，事实上，如果你点开 test 6 的数据，你发现在 \(D_{1000}\) 中，\(1\) 和 \(13\) 的距离不是 \(D_5\) 中 \(1\) 和 \(13\) 的距离 \(3\)，而是 \(2\)，因为可以 \(1\to 14\to 13\)，这时候 \(1\) 和 \(13\) 之间就可以视作连上了一条长度为 \(2\) 的链），\(a\) 与 \(b\) 之间的最短距离。还是分三种情况考虑：

如果 \(a,b\) 都在左子图内，直接递归左子图内，即 \(H(n-1,a,b,2)\)

如果 \(a,b\) 都在右子图内，到右子图内递归，\(H(n-2,a-\text{fib}_{n-1},b-\text{fib}_{n-1},len+1)\)

如果 \(a,b\) 一个在左子图内，一个在右子图内，那么我们计算答案，分三种情况：

\(a\to 1\to |D_{n-1}|+1\to b\)
\(a\to |D_{n-1}|\to|D_{n-1}|+1\to b\)
\(a\to 1\to |D_n|\to b\)

分别讨论一下即可。三种情况的答案均可通过调用 \(F/G\) 函数算出。

总复杂度 \(\Theta(q\log n)\)。

36. CF1572B Xor of 3

怎么评价这个题嘛……过了是过了，但是始终不能理解我的做法/wul，甚至完全不会证它的正确性，反正就硬核着杠了一大坨分讨就过了（

首先，如果 \(1\) 的个数为奇数，那么由于每次操作不会改变序列中 \(1\) 的个数的奇偶性，因此肯定无法将序列中所有元素均变为 \(0\)。

而如果 \(1\) 的个数为偶数，也不一定存在合法解，详情见样例的第三组数据（

那么我们如何判定是否存在合法解以及构造出符合要求的解呢？首先特判掉全部为 \(1\) 的情况，此时必然不存在合法解。而对于更普适的情况，我们先求出每个全部由 \(1\) 组成的连续段，假设为 \([l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]\)，那么我们考虑从左到右依次消除每个连续段，分情况讨论：

如果我们待消除的这个连续段 \([l_i,r_i]\) 长度为偶数，那么如果 \(l_i\ne 1\)，直接依次执行 \(l_i-1,l_i+1,l_i+3,\cdots,r_i-1\) 即可搞定这个连续段，否则依次执行 \(r_i-1,r_i-3,\cdots,l_i\) 也可搞定这个连续段。由于 \(a_i\) 不全为 \(1\)，所以 \(l_i=1\) 与 \(r_i=n\) 不同时成立，因此构造合法。
如果我们待消除的连续段长度为奇数，这部分比较麻烦。设 \(d\) 为当前连续段右端点与下个连续段左端点的距离，继续分情况讨论：
如果 \(d\) 为偶数，那么我们依次执行 \(r_i,r_i+2,\cdots,l_{i+1}-4,l_{i+1}-2,l_{i+1}-4,l_{i+1}-6,\cdots,l_i+2,l_i\) 即可将 \([l_i,r_i]\) 全部变为 \(0\)，同时将下一连续段的长度减一。
如果 \(d\) 为奇数，继续分类讨论：
如果这一段左端点不是 \(1\)，那么依次执行 \(l_i-1,l_i+1,l_i+3,\cdots,r_i-3,r_i,r_i+2,\cdots,l_{i+1-3},r_i-1,r_i+1,r_i+3,\cdots,l_{i+1}-2\)，这样也可达到将 \([l_i,r_i]\) 全部变为 \(0\)，同时将下一连续段的长度减一的效果。
如果这一段左端点是 \(1\)，那么我们会选择用下一段去消当前这一段，分情况讨论：
如果 \(r_{i+1}=n\)，那么无解。
如果 \(r_{i+1}-l_{i+1}+1\) 为奇数，那么我们依次执行 \(r_i,r_i+2,\cdots,l_{i+1}-3,r_{i+1}-1,r_{i+1}-3,\cdots,l_i\)，这样可以将两段同时消没。
如果 \(r_{i+1}-l_{i+1}+1\) 为偶数，那么我们依次执行 \(r_i,r_i+2,\cdots,l_{i+1}-3\)，这样可将两段合并起来，作为新的 \([l_{i+1},r_{i+1}]\)。

于是这道思维题成功被我做成了一道大分类讨论题（大雾

时间复杂度线性。

37. CF1572C Paint

看到这种对一个连续段进行个啥操作的题，我们通常可以想到区间 DP。此题也不例外，我们设 \(dp_{l,r}\) 表示最少进行多少次操作即可将 \([l,r]\) 全部变为 \(a_r\)，思考如何转移：

\(dp_{l,r}\leftarrow\min(dp_{l+1,r},dp_{l,r-1})+1\)，很容易想到。
枚举端点 \(a_i=a_r\)，那么 \(dp_{l,r}\leftarrow dp_{l,i}+dp_{i+1,r}\)，也就是将序列拆成两段分别染色然后合并的套路。这样转移看似复杂度不对，但由于题目保证每种颜色最多出现 \(20\) 次，因此我们可以通过记录 \(pre_i\) 表示 \(i\) 前面离 \(i\) 最近且颜色与 \(i\) 颜色相同的位置，这样转移可以做到 \(20n^2\)。

容易发现所有最优策略都可以通过以上两个操作或者通过针对以上两个操作的调整得到，因此上述 DP 的正确性是可以保证的，复杂度 \(20n^2\)。

38. CF1572D Bridge Club

乍一看到这个题我顿时乐了，\(Q_n\) 按 __builtin_parity 染色之后显然是一个二分图，因此原题等价于二分图最大权匹配，直接费用流……

然后一看数据范围，\(n\le 20\)，这意味着点数 \(\le 2^{20}\)，顿时傻眼，玩个锤子（

事实上我们发现 \(m\le 200\)，因此我们猜测可能在最大权匹配上的边数并不是太多，大概顶多是 \(m\) 或者 \(mn\) 级别的，事实的确如此，可以证明有用的边数上界为 \(m(2n-1)\)，因为减少一条边最多减少 \(2n-1\) 个匹配，故随便取 \(m(2n-1)\) 条边必然存在一个大小为 \(m\) 的匹配。

这样一来事情就容易许多，直接贪心地找最大的 \(m(2n-1)\) 条边，把涉及到的点作为关键点拎出来跑费用流即可。注意找最大的 \(m(2n-1)\) 条边不能使用堆，最好使用 nth_element，否则可能会 MLE（

39. P6663 [POI 2019] Układ scalony

咦？怎么学校模拟赛的题也混到我博客里了（

首先不难发现构造出的树的直径有个下界，考虑如何求出这个下界，显然这个下界不低于 \(n+m-2\) 对吧，因为 \((1,1)\) 和 \((n,m)\) 的距离就已经达到了 \(n+m-2\)，因此我们肯定尽量希望直径长度尽可能接近这个值。可以发现，如果 \(n\) 为奇数，那么我们可以按照如下的方式使树的直径达到 \(n+m-2\)。

对于 \(m\) 为奇数的情况也是同理，只需在上图中将图关于 \(y=x\) 进行一次翻折即可。

而 \(n,m\) 均为偶数的情况，通过观察 \(n=m=2\) 以及 \(n=2,m=4\) 的情况我们大胆猜测，无法构造出直径为 \(n+m-2\) 的方案，因此对于 \(n,m\) 为偶数的情况，直径的下界就是 \(n+m-1\)。

接下来考虑如何根据直径下界构造出合法的解，下面不妨假设 \((n-1)m\) 为偶数，也就是说如果 \(n,m\) 中至少有一个为奇数，那么 \(n\) 为奇数。考虑分情况讨论：

若 \(d\le 2(n-1)+(m-1)\)，那么我们在只需在上图的基础之上稍微做一些改动，有以下两种可能：

如果 \(d\le (n-1)+(m-1)+\dfrac{n-1}{2}\)，那么我们断开 \((\dfrac{n+1}{2},1)\) 与 \((\dfrac{n+3}{2},1)\) 之间的边，连上 \((\dfrac{n+3}{2},1)\) 与 \((\dfrac{n+1}{2}-(d-(n-1)-(m-1)),1)\) 之间的边。
如果 \(d>(n-1)+(m-1)+\dfrac{n-1}{2}\)，那么我们断开 \((\dfrac{n+1}{2},1)\) 与 \((\dfrac{n+3}{2},1)\) 之间的边，连上 \((\dfrac{n+3}{2},1)\) 与 \((1,1)\) 之间的边。再断开 \((\dfrac{n+1}{2},m)\) 与 \((\dfrac{n+3}{2},m)\) 之间的边，连上 \((\dfrac{n+3}{2},m)\) 与 \((\dfrac{n+1}{2}-(d-((n-1)+(m-1)+\dfrac{n-1}{2})),m)\) 之间的边。

直接用这些公式描述连断边的情况可能不太直观，借助下图 \(n=5,m=6,d=12\) 的构造可能可以更好地理解。

若 \(d>2(n-1)+(m-1)\)，那么我们先从 \((n,1)\) 开始，连接 \((n,1),(n-1,1)\) 的边、\((n-1,1),(n-2,1)\) 的边，……，\((2,1),(1,1)\) 的边，\((1,1),(1,2)\) 的边，\((1,2),(1,3)\) 的边，……，\((1,m-1),(1,m)\) 的边，\((1,m),(2,m)\) 的边，\((2,m),(3,m)\) 的边，……，\((n-1,m),(n,m)\) 的边，然后在中间部分反复徘徊直到直径长度达到 \(d\)，对于剩余的点直接连向它上方的节点即可，例如 \(n=5,m=6,d=23\) 的情况可以按照如下方式构造：

直接模拟即可。时间复杂度 \(\Theta(nm)\)。

启示：有的构造题可以尝试从边界状态入手给出边界状态的构造，然后通过调整得到我们想要的构造。

40. CF991F Concise and clear

我为什么会手贱点开这个分类讨论屑题啊（

分类讨论。记 \(D(x)=\lceil\log_{10}(x)\rceil\) 表示 \(x\) 在十进制表示下的位数，那么一个比较浅显的性质是 \(D(ab)=D(x)=\lceil\log_{10}(ab)\rceil\le \lceil\log_{10}(a)\rceil+\lceil\log_{10}(b)\rceil+1\)，而后者表示将 \(ab\) 写成 “a*b" 这种形式所需要的字符数，这也就说明将 \(ab\) 写成 a*b 的形式肯定是不如直接写 \(ab\) 来得优的，因此稍加分析我们发现最优表达方式无非以下几种：

\(a\)
\(a^b\)
\(a\times b^c\)
\(a\times b^c+d\)
\(a\times b^c+d^e\)
\(a^b\times c^d\)
\(a^b\times c^d+e\)

对于第一种情况，可能的情况显然只可能是 \(n\)，对于第二、三、四种情况我们枚举 \(a,b,c\) 然后更新答案，由于 \(c\ge 2\)，因此 \(b\) 只用枚举到 \(\sqrt{n}\)，直接枚举显然会 TLE，不过如果加上”如果当前 \(a\times b^c\) 所需要的位数大于等于当前最优表示法的位数就 break“这一剪枝就能跑得飞起。对于第六种情况，可能的 \(a,b,c,d\) 并不是很多，可以直接枚举 \(a,b,c,d\)，如果 \(a\) 或者 \(c\) 不是 \(n\) 的质因子就跳过，如果 \(D(a)+D(b)+3\) 大于等于当前最优答案就跳过不枚举 \(c,d\)。对于第 \(5,7\) 种情况，由于当 \(n=10^{10}\) 时答案就是 \(10^{10}\)，而对于其他情况 \(n\) 的位数 \(\le 10\)，如果 \(a,b,c,d,e\) 有一个是两位数，那么 \(a\times b^c+d^e\) 和 \(a^b\times c^d+e\) 的位数就 \(\ge 10\)，不是最优解，因此 \(a,b,c,d,e\) 一定是一位数，直接枚举即可。

41. CF883B Berland Army

首先正反一遍 BFS 求出每个点能填的权值的范围 \([l_i,r_i]\)。

考虑贪心地尽量让每个点填的权值靠近 \(r_i\)，具体来说我们从小到大枚举每个值 \(x\in[1,k]\)，然后用个 set 动态维护下所有 \(l_i\le x\) 的 \(r_i\)，分情况讨论：

如果存在一个 \(i\) 满足 \(r_i=x\) 且 \(i\) 没有被赋值，那么我们将所有这样的 \(i\) 都赋上 \(x\)，使用 set 维护即可。
如果不存在上述 \(i\)，那么我们在 set 中 lower_bound 找出 \(r_i>x\) 且 \(r_i\) 最小的 \(i\)，然后在 \(i\) 上赋上 \(x\)。
如果第二个条件也无法满足，则输出 \(-1\)。

时间复杂度 \(m\log n\)。

42. BZOJ #2264. Free Goodies

一开始以为直接模拟就行了，写了一半才发现相当不对劲……

我们考虑将所有物品按 \(a_i\) 从大到小排序，如有多个 \(a_i\) 相同的则再按 \(b_i\) 升序排序，那么可以发现，如果我们确定了每次 Jan 的选择，那么 Petra 每次的选择都是固定的：取当前没有被选择的物品中最靠前的。

如果我们把 Jan 的选择视作右括号，把 Petra 的选择记作左括号，那么在一个合法的取物品方案中，任意一个前缀中右括号个数必然 \(\le\) 左括号个数，因此我们可将问题转化为一个类似括号序列的东西，即我们贪心地取走 \(\lfloor\dfrac{n}{2}\rfloor\) 个右括号，使得将没有选择的括号都替换为左括号后，得到的括号序列中任意一个前缀的右括号个数 \(\le\) 左括号个数。考虑贪心，每次取出一个可以取的位置中 \(b_i\) 最大的，如果有 \(b_i\) 相同则取 \(a_i\) 最小的，用线段树维护这个贪心即可，具体来说，我们先把已经钦定的位置中，左括号视作 \(1\)，右括号视作 \(-1\)，然后在线段树上二分找到最靠右的 \(\le 1\) 的位置 \(p\)，然后在 \([p+1,n]\) 中查询 \((b_i,-a_i)\) 的最大值即可。

最后还有个小问题：如何处理先后手的问题。不难发现如果先手是 Petya 我们这样直接贪心就是正确的，否则我们考虑添加一个 \(a_i=\infty,b_i=0\) 的物品，然后将先手变为 Petya，并且令 Petya 第一次取的物品不计入 Petya 取的物品的总价值，这样就可以按照上面的过程贪心了。

时间复杂度 \(\Theta(n\log n)\)。

43. P3269 [JLOI2016]字符串覆盖

一道非常神仙的贪心题 %%%%%%%%%%%%%%%%%%%

首先求出每个给出的子串在 \(S\) 中的出现位置，这个可以通过字符串哈希实现，不妨设第 \(i\) 个字符串所有出现位置的左端点为 \(p_{i,1},p_{i,2},\cdots,p_{i,c_i}\)。

考虑如何求出所有字符串覆盖的位置的并的最大值，注意到题目一个非常关键的条件：\(n\le 4\)。考虑枚举所有字符串起点的大小关系，这个 \(n!\) 枚举一下即可，再枚举相邻字符串两两之间是否重叠，同样 \(2^{n-1}\) 枚举一下，考虑如何贪心地对每种情况安排每个字符串的启示问题，对于相邻两字符串 \(i,i+1\)，如果它俩不重叠，那么我们肯定尽量希望 \(i+1\) 放置的位置尽可能靠前，否则我们肯定尽量希望 \(i+1\) 放置的位置尽可能靠后，这个将每个串出现的位置压入一个 set 然后在 set 中 upper_bound 即可找到，这样最大值部分就可以在 \(|S|·n!·2^{n-1}\) 的时间内解决。

接下来考虑如何求所有字符串覆盖的位置的并的最小值，首先我们踢掉 \(n\) 个子串中所有包含于另一个子串的子串，因为由于我们求的是最小值，我们肯定会将这样的子串覆盖在包含它的那个子串的位置上最优，此时这样的字符串不会对答案产生任何影响。这样我们可以设计出一个 DP：\(dp_{i,j}\) 表示目前选择了 \(j\) 中的字符串，并且目前选择的字串中，右端点最大的字符串的出现位置的右端点为 \(i\)，覆盖的位置的并的大小的最小值，转移就枚举右端点为 \(j\) 的字符串是啥，设为 \(x\)，有两种转移：

\(dp_{i,j}\leftarrow dp_{k,j-\{x\}}+len_x\)，其中 \(len_x\) 为子串 \(x\) 的长度，\(k<i-len_x\)
\(dp_{i,j}\leftarrow dp_{k,j-\{x\}}+i-k\)，其中 \(i-len_x\le k<i\)。

乍一看这个转移式，你可能会以为需要用线段树等结构维护转移，实则不用。可以发现对于上面那种转移，必然有 \(i-k>len_x\)，因此我们把下面那种转移的下界改成 \(0\) 依然可以计算得到正确的 DP 值，这样转移就变成求一段前缀 \(\min\) 的形式，维护两个数组 \(mn1_{i,j}\) 表示 \(\min_{k\le i}dp_{k,j}\)，\(mn2_{i,j}\) 表示 \(\min_{k\le i}dp_{k,j}-k\)，这样可以 \(\mathcal O(1)\) 转移，于是我们就在 \(\mathcal O(|S|·2^{n})\) 的时间内求出了最小值。

44. CF1521E Nastia and a Beautiful Matrix

一道其实还算容易的构造题（？）

首先不难发现对于一个 \(n\times n\) 的矩阵，按照如下方式填能够最大化有值的位置个数：

\[\begin{bmatrix}
*&*&*&*&*&\cdots\\
*&0&*&0&*&\cdots\\
*&*&*&*&*&\cdots\\
*&0&*&0&*&\cdots\\
*&*&*&*&*&\cdots
\end{bmatrix}
\]

其中 \(*\) 表示一个非零值。由此我们可以得到，对于一个 \(n\times n\) 的矩阵，其中最多可以有 \(n^2-\lfloor\dfrac{n}{2}\rfloor^2\) 个非零元素。

但是，\(n^2-\lfloor\dfrac{n}{2}\rfloor^2\ge m\) 并不一定是我们能够将 \(a_1\) 个 \(1\)、\(a_2\) 个 \(2\)、\(a_3\) 个 \(3\)、……、\(a_k\) 个 \(k\) 填入矩阵的充分条件，显然，如果 \(a_1=n^2-\lfloor\dfrac{n}{2}\rfloor^2\)，且 \(n\ge 2\)，那么我们全填 \(1\) 肯定不符合条件 \(2\)。容易发现，我们最多在这 \(n^2-\lfloor\dfrac{n}{2}\rfloor^2\) 个非零位置中，填入 \(n·\lceil\dfrac{n}{2}\rceil\) 个同种元素，这个可以通过对矩阵进行黑白染色 + 抽屉原理证明，构造如下：

\[\begin{bmatrix}
1&1&1&1&1&\cdots\\
*&0&*&0&*&\cdots\\
1&1&1&1&1&\cdots\\
*&0&*&0&*&\cdots\\
1&1&1&1&1&\cdots\\
\end{bmatrix}
\]

因此我们再记 \(mx=\max\limits_{i=1}^ka_i\)，那么 \(n^2-\lfloor\dfrac{n}{2}\rfloor^2\ge m\) 且 \(mx\le n·\lceil\dfrac{n}{2}\rceil\) 是否充分了呢？答案是肯定的。我们依次写下 \(a_1\) 个 \(1\)，\(a_2\) 个 \(2\)，……，\(a_k\) 个 \(k\)，这样可以得到一个长度为 \(m\) 的序列，不妨称之为 \(b_1,b_2,\cdots,b_m\)，那么我们按照如下方式填数：

在 \((1,2),(1,4),(1,6),\cdots,(3,2),(3,4),(3,6),\cdots,(5,2),(5,4),\cdots\)（即所有横坐标为奇数，纵坐标为偶数的格子）中依次填下 \(b_1,b_2,\cdots\)。
填完了横坐标为奇数，纵坐标为偶数的点后，再填横纵坐标均为奇数的点，即 \((1,1),(1,3),(1,5),\cdots,(3,1),(3,3),\cdots\)。
如果这些点填完了还有剩余的数，那就再依次在 \((2,1),(2,3),(2,5),\cdots,(4,1),(4,3),\cdots\)，也就是所有横坐标为偶数，纵坐标为奇数的点中填数。

不难发现，在这样的构造方式下，所有形如 \((2x+2,2y+1),(2x+1,2y+2)\)（也就是禁止填上相同的数的点对们）所填上的数在 \(b\) 序列中的距离都 \(\ge n·\lceil\dfrac{n}{2}\rceil\)，而根据假设不存在 \(>n·\lceil\dfrac{n}{2}\rceil\) 的 \(a_i\)，因此这些点对中填上的数必然不同，因此我们的构造是合法的。

45. CF1073F Choosing Two Paths

一道细节略有点多的树形 dp，不过思想还是很 simple 的（

首先感觉这个东西可以用类似于树的直径的方法搞，因此类比树的直径，我们设 \(f_i\) 表示 \(i\) 子树内距离 \(i\) 最远的点到 \(i\) 的距离。再设 \(dp_i\) 表示一个三元组，其中第一项为 \(i\) 子树内选两条以 \(i\) 为起点的路径，它们重叠部分的最大值，第二项为 \(i\) 子树内选两条以 \(i\) 为起点的路径，它们在重叠部分最长的前提下，覆盖的总距离的最大值，第三项为在前两项都取到最大值的前提下，重叠部分的下端点。那么显然 \(f_i,dp_i\) 可以通过一遍 DFS 求出。

接下来考虑如何求解答案，不难发现最长路径的重叠部分无非两种，要么重叠部分的两个端点是祖先关系，要么不是祖先关系，我们对它们分别讨论，对于前者，我们枚举深度较浅的那个端点 \(x\)，换根 DP 一下求出每个点子树外距离其最远的点与其的距离，这样可以用个 multiset 维护以 \(x\) 为根时，\(x\) 的每个子树内的点与其距离的最大值。这样可以更新答案。对于后者我们枚举 LCA，不妨称为 \(x\)，那么相当于找到 \(dp\) 值最大的两个儿子，multiset 维护即可。

时间复杂度 \(n\log n\)。

46. CF1599A Weights

惊恐，某毛子出的比赛竟然在 CF 上有原题（大雾，指 ISIJ Cup T3

其实 CF 上这场比赛时间晚于 ISIJ2021 杯赛所以大概也没有原题之说/yiw

首先观察样例没有 \(-1\) 的情况因此我们猜测一定存在解，考虑如何构造之。我们先将 \(a\) 数组从小到大排个序，不妨假设 \(a_1<a_2<\cdots<a_n\)，首先如果 LR 交替排列那我们肯定会依次将 \(a_1\) 放入左盘，\(a_2\) 放入右盘，\(a_3\) 放入左盘，依次类推，这样每次放完以后，总重量的绝对值都小于当前摆下的最重的物品的重量，进而符合条件。考虑如果 \(s\) 不等于 \(LRLRLRL\cdots\) 如何处理，我们归纳构造，即从最后一次进行的操作开始往前推，如果最后两次操作对应的字符相同，那我们就将 \(a_i\) 最小的物品放在最后一个，否则我们将 \(a_i\) 最大的物品放在最后，类似于一个双端队列的结构，然后再根据每次操作之后重量较大的是一边决定物品放在哪一边即可。

时间复杂度 \(\Theta(n)\)。

47. CF1599J Bob's Beautiful Array

首先特判掉 \(n=2\) 和 \(n=3\) 的情况，显然 \(n=2\) 时只有 \(a_1=a_2\) 时才有解，解为 \(\{a_1,0\}\)，\(n=3\) 时我们可列出一个三元一次方程组，把三个未知量解出来即可。

考虑 \(n\ge 4\) 时怎么做，显然如果序列中有 \(\ge 1\) 个偶数，那么必定是存在解的，具体构造就是如果偶数个数 \(\ge 3\)，那么找三个偶数 \(x,y,z\)，令 \(a_1+a_2=x,a_2+a_3=y,a_3+a_1=z\)，然后将剩下的数排成一列，不妨称之为 \(b_1,b_2,b_3,\cdots,b_{n-3}\)，然后令 \(a_{i}+a_{i+1}=b_{i-2},i\in[3,n-1]\) 即可，否则我们找到一个偶数 \(x\) 和两个奇数 \(y,z\)，然后重复上面的操作即可。

如果 \(a\) 数组中只有奇数怎么办呢？设答案数组为 \(x\)，那么我们考虑建立一张图，如果 \(x_i+x_j\) 在 \(a\) 序列中出现过，那么我们就连一条 \(i,j\) 之间的无向边，不难发现这张图中至少有 \(n\) 条边，也就是说其中至少有一个环，我们考虑一个环意味着什么，显然这个环中数的个数必须是偶数，而如果我们把这个环黑白染色，那么不难发现，黑色的点对应的 \(x_i\) 之和与白色的点对应的 \(x_i\) 之和相同，也就是说对于 \(a_i\) 全是奇数的情况，解存在的必要条件是存在两个不相交的集合 \(S,T\)，满足 \(S\) 中所有元素之和与 \(T\) 相同。那这个条件是否充分呢？显然是充分的，我们只要将剩余的数按照存在一个偶数的情况排列即可。

于是问题转化为如何求解符合要求的两个集合 \(S,T\)，直接貌似背包复杂度似乎有些拉垮，不难发现一个性质：当 \(n\ge 28\) 时必然存在解，因为对于 \(n=28\) 的情况，有 \(\dbinom{28}{14}\approx 4\times 10^7\) 个大小为 \(14\) 的集合，而大小为 \(14\) 的集合中，不同的元素和只有 \(14·10^6<2\times 10^7\) 种，根据抽屉原理，必然存在两个大小为 \(14\) 的集合，它们当中的元素之和相同，而如果我们扣掉这两个集合公共的部分，剩余部分依然满足元素之和相同，进而符合条件。

这样一来我们的思路就很明显了：取前 \(\min(n,28)\) 个元素，然后折半搜索前 \(\lfloor\dfrac{n}{2}\rfloor\) 个元素在 \(S\) 中的部分以及 \(T\) 中的部分，把它们的大小差和元素之和的差压入一个 map 中，然后折半搜索后半部分的时候在左半部分的 map 中查找一下是否即可，时间复杂度大概是 \(3^{14}·14\)，可以通过。

注意：此题略有些卡常，一开始使用 C++11 自带的 unordered_map 被卡了，换成手写的哈希表才得以通过/dk

48. CF871E Restore the Tree

首先非常明显的一点是，根据每个点到关键点的距离我们可以确定每个关键点具体是什么——因为它就是到该关键点距离为 \(0\) 的点。当然如果这样的点不唯一咱就直接输出 \(-1\) 即可。在下文中为了方便起见我们称这些关键点为 \(p_1,p_2,\cdots,p_k\)。

我们不妨将树根定在以 \(p_1\)，这样我们只要确定了每个点的父亲，就可以确定整棵树。下面我们的任务就是找到每个点的父亲，一个 trivial 的 observation 是，对于 \(p_1,p_2,\cdots,p_k\) 构成的虚树上的所有点，它们的父亲是很容易确定的，因为对于一个 \(p_i\)，\(p_1\to p_i\) 路径上所有点组成的集合等于 \(\{x|d_{1,x}+d_{i,x}=d_{1,p_i}\}\)，这个遍历一遍即可求得，又显然这些点的 \(d_{1,x}\) 互不相同，因此我们可以轻松获取这些节点的父子关系——当然，如果这其中的父子关系出现冲突，我们需输出 \(-1\)。

接下来考虑如何钦定剩余的点，显然对于每个不在虚树上的点 \(x\)，我们可以找到这个点到根路径上深度最深的且在虚树上的点 \(pt_x\)，这个就枚举所有关键点 \(i\)，然后根据 \(d_{1,x}+d_{1,p_i}-2d_{1,\text{LCA}(p_i,x)}=d_{i,x}\) 得到它们 LCA 的深度，进而知道它们的 LCA 是谁，那么我们要求的 \(pt_x\) 就是所有 LCA 中深度最深的。

我们考虑把所有不在虚树上的点 \(x\) 都存在 \(pt_x\) 的 vector 里，然后遍历虚树上的每一个点，将其 vector 中的点按深度从小到大排序，然后考虑这些点的深度的每一个连续段，如果相邻两个连续段中点的深度相差超过 \(1\) 那么答案是 \(-1\)，否则我们把这一连续段中的点挂在上一连续段中任意一个点下面即可。

时间复杂度 \(nk\log n\)。

不过 u1s1 这道题的数据好像除了 test2 没有 \(-1\) 的点，所以 \(-1\) 的情况你想咋判就咋判反正 test2 那么弱也不太可能 WA（大雾，/xyx

49. P7915 [CSP-S 2021] 回文

没错，这就是 CSP 时候把我送走的题（

绿题？绿题！绿题！！/fn/fn

我们考虑枚举第一次操作是 L 还是 R，不妨设之为 \(c\)，那么我们可以知道最后一次取走的是哪个数，如果我们把序列从这个数所在的位置劈开，显然可以得到两个双端队列，然后我们就维护四个指针在这两个双端队列中贪心，即我们枚举到第 \(i\) 位时，先尽量令 \(s_i=s_{2n+1-i}='\text{L}'\)，看看是否可行，如果不可行就 LR，如果还不可行就 RL，如果还不可行就 RR，如果再不可行则说明第一次操作为 \(c\) 的情况不合法。如此贪心下去即可。

所以说，不少与双端队列/队列取数的题都可以考虑贪心，只不过对于此题而言，只考虑眼前的利益，也就是让每一步都最优是正确的，但是有些题目就不一定了，比如说……（剧透 ing）

时间复杂度 \(\Theta(Tn)\)。

50. CF627F Island Puzzle

首先特判掉树的情况，显然此时移动方案是唯一的，简单判断一下即可。

环套树的情况，我们不妨先以初始状态中 \(0\) 所在的节点为根。可以发现假设环上的点在树上的路径为 \(u\to v\)，那么不难发现绕着环交换的本质是将一个点单独拎出来，然后剩余的点做一个轮换，因此我们考虑先求出将 \(0\) 的点由初始状态中的位置换到目标状态的位置时，得到的序列张什么样，不妨设之为 \(\{c_n\}\)，那么一个显然的性质是，只有以下两种情况时才有解：

\(c_i\ne b_i\) 的点组成一条祖先到后代的链
\(c_i\ne b_i\) 的点组成两条祖先到后代的链，且这两条链链顶节点的父亲节点相同。

这个可以一遍 DFS 判断，这样我们可以知道添加的边是什么，从而确定要轮换多少轮。那么有两种轮换方法，要么 \(u\to v\)，要么 \(v\to u\)，分别计算一下取个 \(\min\) 即可，还有一部分是从初始节点到这个环再到终止节点的步数，显然如果这个环中有节点在初始节点到终止节点的路径上那肯定顺路走过去最优，否则我们要么一开始走到环那么还原环上的点，要么到达终止节点以后还原环上的点，分别计算一下取个 \(\min\) 即可。

时间复杂度线性。

贪心/构造/DP 杂题选做Ⅱ的相关教程结束。