自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:29:00，当前版本为作者最后更新于2020-11-29 11:52:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

真不会写题面了，出题人语文没救/ll

算法 1：

输出 $q$ 个 $0$，复杂度为读入复杂度 $O(n+q)$。

当然对于链是正确的，期望得 $1$ 分。

算法 2：

对于菊花，只能从两个方向走，分类讨论一下。

复杂度 $O(n+q)$，期望得 $9$ 分。

算法 3：

将每一个区域看作一个点建图。

考虑每一条直线，将两侧的区域连一条代价为 $1$ 的边。

每次询问跑 BFS 即可。

时间复杂度 $O(nq)$，期望得 $20$ 分。

算法 4：

当树为完全二叉树时，可以将区域按照最顶上的点进行编号。

然后有一个 observation：对于一个点，在最优移动中，最顶上的点一定一直是 $u$ 或 $v$ 的祖先。

由于这是二叉树，所以直接按区域编号做一个暴力的 dp 的复杂度是 $O(\log n)$。

于是就可以做了。

期望得 $20$ 分。

当然如果你把区域换成用边表示，缩掉链，并在 dp 的方程上稍微做一点修改就可以过掉前面的所有点并获得 $40$ 分。

算法 5：

受到算法 4 的启发，考虑将 $u\rightarrow \text{lca}(u,v)$ 和 $v\rightarrow \text{lca}(u,v)$ 单独提取出来。

如果能做出这两条链的结果，那么就变成了菊花上的问题。

那么怎么求这两条链的结果呢？

首先把链提取出来，然后我们发现，不与这条链直接相连的节点都是没有用的，因为过它们的边肯定不优于过直接与链相连的边。

现在就可以考虑一个倍增形式的 DP。

定义一条边的「左区域」为子节点编号更小的区域，同时另外一个区域就是「右区域」。

设 $dp_{u,k,0/1,0/1}$ 表示从 $u\rightarrow f_u$ 的边的左区域（ $0$ ）/右区域（ $1$ ）走到 $f_u^{2^k}\rightarrow f_u^{2^k+1}$ 的左区域（ $0$ ）/右区域（ $1$ ）的最小代价。

那么如何由 $dp_{u,k-1}$ 转移至 $dp_{u,k}$？

可以分类讨论是否跨过中间的边，然后把两条路径连接起来。

于是我们就有如下转移：（由于比较复杂，所以就贴代码了）

Segnode operator + (const Segnode& b) const {
	Segnode res;
	int v1 = Min(b.lldis, b.rldis + 1), v2 = Min(b.lldis + 1, b.rldis), v3 = Min(b.lrdis, b.rrdis + 1), v4 = Min(b.lrdis + 1, b.rrdis);
	res.lldis = Min(lldis + v1, lrdis + v2);
	res.lrdis = Min(lldis + v3, lrdis + v4);
	res.rldis = Min(rldis + v1, rrdis + v2);
	res.rrdis = Min(rldis + v3, rrdis + v4);
	return res;
}

其中 lldis 就是左区域到左区域的最短路径长度，lrdis 是左区域到右区域的最短路径长度，rldis 是右区域到左区域的最短路径长度，rrdis 是右区域到右区域的最短路径长度。

转移思路可以理解为不跨过中间的边，就是左接左，右接右；跨过中间的边，就是左接右，右接左，然后再加 $1$ 代表跨过中间的边产生的代价。

那么边界 $dp_{u,0}$ 就直接讨论一下 $f_u$ 的度数即可。

int lw = faid[i] - 1, rw = g[fa[i][0]].size() - faid[i];
dp[i][0].lldis = Min(lw, rw + 2);
dp[i][0].lrdis = 1 + Min(lw, rw);
dp[i][0].rldis = 1 + Min(lw, rw);
dp[i][0].rrdis = Min(lw + 2, rw);

于是我们对每一组询问倍增，然后就变成了菊花上的询问，故用菊花的方式 $O(1)$ 合并即可。

时间复杂度 $O((n+q)\log n)$，期望得分 $99$ 分。

算法 6：

在算法 5 的基础上继续改进，考虑长链剖分。

类似树上 $k$ 级祖先，保存链顶往上链长个 dp 值和往下链长个 dp 值。

剖分完之后再结合倍增，问题转化为区间求和，但是信息不可减，不能交换，只有结合律。

直接上 sqrt tree，复杂度为 $O(n\log n+q)$。

细节非常多，尤其要注意在预处理时倒序求和（$\text{sum}(l,r)=a_r+a_{r-1}+\cdots+a_l\neq a_l+a_{l+1}+\cdots+a_r$），如果顺序错误（应该）会被第二个样例卡掉。

还有一些神奇的卡常方式，例如链长为 $1$ 的长链不需要保存，以及将单链缩为一个点。

然后要注意 sqrt tree 的写法，如果你直接用 vector 之类的东西去建树那么时空稳稳炸飞，更好的写法是按层开数组。

然后是一个时间上的卡常，由于在询问的链的长度的二进制表示中 1 位数量比较小的时候倍增快于正解，所以正解做了一个分治，在 $k$ 的二进制表示只有 $\leq 3$ 个 $1$ 的时候直接倍增。

最后，在做完上面的卡常之后，可以保证 sqrt tree 查询的区间长度 $\geq 15$，所以 分块只需要分到块长等于 $8$。这样可以砍下很多空间。

更进一步，链长 $\leq 7$ 的长链也全都不需要存了。

巨量细节和卡常也是我为什么只给这个 subtask $1$ 分（

期望得分 $100$ 分。

核心代码

顺便推一下 Ace Combat 系列，挺好玩的，而且 7 代支持 PC，有意愿的可以一试（

AC6 Ace Of Aces M09 也是值得一试的一作，号称是皇中皇极端变态的难度的巅峰，如果有神仙过了给我来一组图（