本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp
题意:给出n个点的无根树,然后其他每个点可以走出的最远距离(从该点出现走出一条最长的简单路径)。然后按顺序排好点1,点2,点3,点4的最远距离,即得到一个序列。给一个限制值m,在序列中找一段最长的连续区间,使得区间内最大值和最小值的差值要<=m,问这样的区间长度是多少
这题主要是求每个点能走出的最远距离,对于后面那个查询最长区间,是怎么做都可以的。
设一个点能走出的最远距离为d[u],两次dfs即可求出,非常典型的树dp技巧,就不详细说了
对于查询最长区间,就是使用双指针的方法,一开始都指向1,然后询问一些双指针包括的区间,查询一些区间的最大和最小值,如果差<=m,那么说明这个区间是合法的,尝试去更新答案,并且将尾指针向右移动,因为显然可以尝试去增加长度。如果差 > m,那么说明这个区间不合法,将头指针向右移动。所以解决的主要问题就是每次都要询问区间的最大值和最小值,这个,可以用RMQ,但是这题,数据太大,RMQ的dp数组开下去会MLE,所以就用什么?没错暴力…………
网上很多报告都说线段树和单调队列,确定单调队列应该是最快的,但是线段树未免小题大做了,速度非常慢,比暴力慢多了
1 |
|
线段树的代码,只给出建树和查询部分
1 | struct SegTree{ |