Freezing

好像不是题解，算是记录。 记一个 Trick：当求路径边权的中位数的最大值的时候，可以先二分一个答案 \(mid\)，然后把大于 \(mid\) 的边设为 \(1\)，否则设为 \(-1\)。这样只需要看路径长度是否大于零就可以判断出有没有中位数大于等于 \(mid\) 的情况了。 当然类似到求一个 ......

# CF150E Freezing with Style ## 题意 给定一颗带边权的树，求一条边数在 $[L,R]$ 之间的路径，并使得路径上边权的中位数最大。输出一条可行路径的两个端点。 注：此处 $1,2,3,4$ 的中位数为 $3$ ，而非 $2$ 或者 $2.5$ 。 ## 题解 首先用中 ......

CF150E Freezing with Style $\text{difficulty}=2.5,4$。 $\text{tags}=点分治,单调队列,二分$ 注意到中位数考虑直接二分答案 $k$，令权值 $\ge k$ 的边的新权值为 $1$，权值 $<k$ 的边的新权值为 $-1$，那么如果存在 ......