04 2016-07 HDU 2586 How far away ？(LCA离线算法) 紫杉 LCA 2016-07-04 3,287 传送门：点我~~ 题意：有n个房子，用n-1条边连接起来，接下了有m次询问，询问两个房子之间的距离是多少。先建一棵树，然后求出每一点i到树根的距离dis[i],然后每次询问a，b之间的距离=dis[a]+dis[b]-2*dis[LCA(a,b)]，LCA(a,b)即是a，b的最近公共祖先。 #include<bits/stdc++.h> us... LCA,Tarjan离线算法LCATarjan离线算法 07月04日 3,287
