【数据结构】【图论】[JZOJ4864] Dash Speed【无实现】

前端之家收集整理的这篇文章主要介绍了【数据结构】【图论】[JZOJ4864] Dash Speed【无实现】前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

Description

给出n个点的一棵树,每条边有一个承受区间 [L,R]
接下来m个询问,每次询问一个x,表示需要回答所有承受区间包含x的边组成的森林的直径
n,m<=70000,l,r<=n

Solution

看上去不可做的样子

事实上可以用分治的思想,弄出一棵线段树来,对于一条边就将它挂在线段树对应的log个区间上

那么现在就相当于单点查询
我们可以在一开始就将整棵线段树DFS一遍,然后用按秩合并的并查集维护联通块,合并的时候维护直径,撤销就在合并的位置记一下就行了

时间复杂度大概是 O(Nlog2N)

猜你在找的数据结构相关文章