自动搬运

查看原文

来自洛谷，原作者为

	加藤惠 所以我小丑 他是大师

搬运于2025-08-24 22:30:19，当前版本为作者最后更新于2021-04-15 07:22:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先来考虑如果树是条链怎么做。

首先注意到如果第一个序列选了区间 $[l,r]$，那么第一个序列的第 $l − 1$ 个位置和第 $r + 1$ 个位置肯定在第二个序列中选了，否则显然移动 $l$ 或者 $r$ 能得到一个更优秀的解。

考虑对于第一个序列分治，每次需要计算当 $l$ 落在 $[l, mid]$ 和 $r$ 落在 $[mid + 1, r]$ 中的答案。

处理出前半部分每个后缀和后半部分每个前缀的第二个序列的最优选择方案，注意到合并两者的时候第二个序列的选择方案就是处理出来两者的最优选择方案的交，按第一维排序后，数据结构维护第二维的就行。

到树上的话把分治换成点分治就行。

还有一个问题是如果树上选的一条链的一端是叶子不能套用这个做法，需要特判。

记叶子个数是 $k$，时间复杂度为 $O(n\log n\log m+nk\log n+m)$。