CF150E Freezing with Style

题意

给定一颗带边权的树，求一条边数在 \([L,R]\) 之间的路径，并使得路径上边权的中位数最大。输出一条可行路径的两个端点。

注：此处 \(1,2,3,4\) 的中位数为 \(3\) ，而非 \(2\) 或者 \(2.5\) 。

题解

首先用中位数惯用套路二分，将小于 \(mid\) 的设为 \(-1\)，大于等于 \(mid\) 的设为 \(1\) 。

一条路径满足条件当且仅当路径和非负。

首先这是一个路径统计问题，用点分治。

注意到有一个路径长度 \([L,R]\) 的限制，多加一维用线段树，即可做到 \(O(nlog^3n)\)，过不了。

这里有一个比较新的方法，用单调队列来解决这个问题。

我们处理完一个子树之后得到一个数组 \(f_i\) 表示当前子树深度为 \(i\) 的链前缀最大值。
我们用 \(g_i\) 表示前面子树为 \(i\) 的链前缀最大值。
处理完一个子树之后我们要枚举深度 \(j\)，询问 \([L-j,R-j]\) 中 \(g_i\) 的最大值拼上去。
显然 \([L-j,R-j]\) 是一个滑动窗口状的东西，每次操作最坏都是前面的子树最深的深度。
如果直接这样做的话，会被叉成 \(O(n^2)\) 。

有一个显而易见又很神奇的操作来优化这个东西。
对于一个中转点我们将其子树按照最深的点排序，依次处理。
容易发现每次滑动窗口操作的时间复杂度不会超过当前子树的深度。
注意到做了一个排序，点分治中每个点只会成为一次中转点，所以排序的总数是边数级别的。
所以点分治一次的时间复杂度仍是 \(O(nlogn)\)，总时间复杂度 \(O(nlog^2n)\)，code