P7484 再生之青

加藤惠 · 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)。