主题

主题

 
   

Dash Speed

原题:(权限限制没有链接)

题目描述

比特山是比特镇的飙车圣地。在比特山上一共有n 个广场,编号依次为1 到n,这些广场之间通过n-1 条双向车道直接或间接地连接在一起,形成了一棵树的结构。

因为每条车道的修建时间以及建筑材料都不尽相同,所以可以用两个数字li; ri 量化地表示一条车道的承受区间,只有当汽车以不小于li 且不大于ri 的速度经过这条车道时,才不会对路面造成伤害。

Byteasar 最近新买了一辆跑车,他想在比特山飙一次车。Byteasar 计划选择两个不同的点S与T,然后在它们树上的最短路径上行驶,且不对上面任意一条车道造成伤害。

Byteasar 不喜欢改变速度,所以他会告诉你他的车速。为了挑选出最合适的车速,Byteasar 一共会向你询问m 次。请帮助他找到一条合法的道路,使得路径上经过的车道数尽可能多。

输入输出格式

输入格式:

第一行包含两个正整数n,m,表示广场的总数和询问的总数。

接下来n-1行,每行四个正整数ui,vi,li,ri,表示一条连接ui 和vi 的双向车道,且承受区间为[li,ri]。

接下来m 行,每行一个正整数qi,分别表示每个询问的车速。

输出格式:

输出m 行,每行一个整数,其中第i 行输出车速为qi 时的最长路径的长度,如果找不到合法的路径则输出0。

输入输出样例

输入样例#1:

5 3

3 2 2 4

1 5 2 5

4 5 2 2

1 2 3 5

1

2

3

输出样例#1:

0

2

3

说明

n,m<=7*10^4

(来源:BZOJ2016NOIP十连测)


个人解法:

把询问排序,把边按照速度下限排序。

之后我们扫描每一个询问,把速度下限小于或者等于当前询问的边加入进来,然后我们需要删去速度上限已经小于当前询问的边。

所以我们需要一种数据结构维护加入的边,堆可以完成。

这样我们只需要维护连通块的直径的长度即可。

但是本蒟发现既加边又删边,不好维护(也许是本蒟较菜)……

于是我们需要一种结构,可以转删边操作为撤销加边操作

所以想到线段树分治。把边挂在节点上,就可以使用并查集来维护连通块的直径了。按秩合并,可以支持撤销。

关于合并连通块,直径的维护:

记录2个连通块的直径端点是哪4个点。合并后的连通块的直径的端点必然是这4个中的2个。

至于证明,画画图就好了。


代码如下:

https://code.csdn.net/snippets/2292879

 
 
评论