题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2586
题目是说:N个顶点形成树,接下来有M次询问两个顶点间的距离~
解题思路:用Tarjan脱机最小公共祖先算法(
然后计算两个顶点到根部的距离加起来与他们公共祖先到根部的距离乘以2的绝对值
Dist(u,v) = abs(dist[u]+dist[v]-2*dist[ancestor[v]]);
Tarjan算法我是看着
晒一下我的代码:
原文:大专栏 HDU 2586 How far away ?