杂题选做-3
#21 P9755
题目传送门
首先，看上去这个题直接不是很友好，我们考虑二分转为判断性问题。
然后一个这类在树上 topo 遍历每一个节点的最优方案类问题有一个 Trick：我们找出当前最优的节点，将其与其父亲合并。
具体地，在确定一个答案 \(T\) 之后，我们可以在 \(O(1)\) 的时间内求出或通过二分在 \(O(\log n)\) 的时间内每一个点的最晚访问时间 \(t_i\)。具体地，我们可以先预处理每一个节点的一次函数值什么时候小于 \(1\)，优先统计 \(1\) 的贡献，然后对剩余部分我们就考虑对 \(b_i\) 和 \(c_ix\) 分别求和。
然后我们只需要考虑两个问题：
-
怎么判断一个节点是否比另一个节点更优（确定排序规则）；
-
怎么合并一个节点和其父亲；
我们优先思考第二个问题。我们在合并完一个节点后，这个新节点的最晚的访问时为 \(t_i-1\)。因为 \(t_i\) 是合并前的最小时间点，所以 \(t_i-1\) 也一定是合并后的最小时间点。
因此我们发现可以简化上述流程：直接找到当前时间点最小的点，然后直接把它到根的所有未访问点访问。
时间复杂度为 \(O(n \log V \log n)\)，可以通过数学推导优化到 \(O(n \log V)\)。
#22 P8817
题目传送门
看到 \(n \le 2500\)，且边权为 \(1\)。我们就知道可以在 \(O(n^2)\) 的时间内用 01 bfs 预处理出任意两点间的距离。
然后我们考虑一个问题，假如我们确定了 \(b,c\)，那么我们希望取到 \(b\) 可达的点中，权值最大的点，和 \(c\) 可达的点中，权值最大的点。
但是这两个点可能相同，或者与 \(b,c\) 相同，但是可以确定的是，我们只需要枚举前 \(3\) 大的节点即可。
时间复杂度为 \(O(n^2)\)。