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

Description

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

Solution

看上去不可做的样子

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

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!