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

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

Description

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

Solution

看上去不可做的样子

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

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

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

大佬总结

以上是大佬教程为你收集整理的【数据结构】【图论】[JZOJ4864] Dash Speed【无实现】全部内容，希望文章能够帮你解决【数据结构】【图论】[JZOJ4864] Dash Speed【无实现】所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。