Wannafly模拟赛2 C alliances（dfs序+二分）

题目

题意

　　由n个点组成一个树，有m个帮派，每个帮派由一些个点组成，这些点以及它们两两路径上的所有点都属于该帮派的管辖范围；

　　有q个询问 v {S} ，表示现在{S}中的帮派联合起来，它们所有点对的两两路径上的所有点都属于该联盟的管辖范围，回答从v点到管辖范围点的最短距离

　　n<=5e5,m<=5e5,q<=5e5

分析

　　首先来考虑只有一个帮派，并不形成联盟的情况，假设我们要询问v点和这个帮派管辖点之间的最短的距离

　　这些点形成的管辖区域一定是以它们共同lca为根的一个树（是lca子树的一部分）

　　我们来考虑v点和这个树的关系

　　　　1)如果v点在以lca为根的子树外面，即dfn[v]<dfn[lca]或者dfn[v]>rtime[lca]，这样容易发现此时的距离就是dist(v,lca)

　　　　2)如果v点在以lca为根的子树里面，那这时我们可以将这些点按照dfs序进行排序，然后将dfn[v]在排序结果中lower_bound找到dfs序离v最近的两个点x,y，那么结果就是$min(dist(v,lca(v,x)),dist(v,lca(v,y)))$

　　现在再来考虑联盟的情况

　　实际上，我们可以将每个帮派的管辖情况都缩成一个点，那么实际上这些帮派代表点形成一个新的“总帮派”，我们只需要在这个总帮派上进行我们之前同样的操作就ok了

　　其实并不需要真正的缩点，容易发现对于一个帮派里所有点，任意选一个做为代表点，都不会影响结果，所以只需要任意挑出一个代表点就行了

　　这题n有5e5，如果直接dfs建图会爆栈，需要手写

巴特西