【CJOJ130】中位数

题目描述

求带边权的树上的长度为 L~R 的中位数最大的路径(有多个中位数时取最大的那个)。

路径的长度是指边的条数。

输入数据

第一行三个数,N,L,R。

接下来 N-1 行,每行两个数 x,y,z,表示 x 和 y 之间有一条权值为 z 的边。

输出数据

仅一行一个数,表示最大的中位数。

数据约定

30% : N <= 1000

100 : N <= 10 ^ 5, 0 <= 权值 <= 10 ^ 7

题解

貌似是真正意义上的第一次写点分治。。

上次写,一个是照着打的,另一个是连线段树都没用= =

一开始以为和上一次一样做的。。然后发现复杂度不对= =

黄楚和我讲用线段树。。然后想了一会大概明白了

首先是二分答案m,每次将大于等于m的边标记为1,否则为-1

那么问题就是找出一条长度在[L,R]的路径使得边权和非负

所以用线段树记录深度为某个区间的边权和最大值

还是打的ZKW。。发现ZKW真的爽 又短又快

(代码改了一下风格233)

说点什么

您将是第一位评论人!

提醒
wpDiscuz