不要问我为什么标题这么毒瘤

题目描述

你有一棵 $n$ 个点的树( $n \leq 5000$),树上第 $i$ 个点有权值 $a_i$。选取 k 条互不相交的链,其上所有点权值和为 $s$,最大化 $\dfrac{s}{k+1}$。

现在出题人觉得这样太简单了,于是给了你一个区间$[0,T]$ 和一个模数 $m$。你现在可以在区间内选择一个整数 $x$,令 $a_i=(a_i+x) \ mod \ m$。

求最大的可能答案。

思路

我们先不考虑修改点的权值,那这道题就是分数规划。二分最后的答案 $ans$,那么选择一条新链的代价是 $ans$,树形dp 即可,时间复杂度 $O(nlogn)$。

现在我们考虑修改权值的操作。最暴力的修改是对于每一个合法的 $x$ 都计算一遍答案。由于 $T$ 很大,所以爆炸。

发现对于每一个 $a_i$,都有一个可能的最优 $x_i$ 使得修改权值后 $a_i$ 达到最大的可能值 $m-1$。预处理出最优 $x$ 序列,长度为 $n$。这样就是 $O(n^2logn)$ 了。

最后我们发现,对于 $x_i$,先验证当前最大的答案 $ans_i$ 在此时是否可行,如果不行就跳过。这样我们相当于从 $x_i$ 序列中提出了一个子序列进行二分。我们可以 $random \ shuffle$ 这个 $x$ 序列,那么期望的 $LIS$ 长度就是 $logn$ 级别的,这样最后的复杂度就是 $O(n{(logn)}^2)$ 了。

代码