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

Description

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

Solution

看上去不可做的样子

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

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

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

相关文章
相关标签/搜索