题目
http://acm.hdu.edu.cn/showproblem.php?pid=6110
分析
注意到，若干条路径的交一定也是条路径
我们可以维护一个线段树，seg[l..r]存着第l条~第r条路径的交（用起点和终点表示即可）
维护的时候就是两个孩子对应的路径求个交作为自己的交
询问的时候也是讲询问分成若干段，然后逐个合并
于是我们只要解决两条路径求交的问题就可以了
设两个lca分别是c1,c2，dep[c1]<=dep[c2]
设a1与a2的lca为d1，设a1与b2的lca为d2，设b1与a2的lca为d3，设b1与b2的lca为d4
并设dep[d1]<=dep[d2]<=dep[d3]<=dep[d4]
画图可以发现，存在路径交的充要条件是dep[d4]>=dep[d3]>=dep[c2]
路径交就是d4->d3这一段
时间复杂度是O(nlog^2n)
如果求lca用rmq来求的话就是O(nlogn)了
rmq求lca就是求dfs序数列，u,v两点的lca就是dfs序数列中dfstime[u]..dfstime[v]中深度最小的那个位置
这样查询是O(1)的
