ZOJ 3195 Design the city (lca + st )

ZOJ 3195 Design the city

给出n个区域,有n-1条路去连接这些区域,显然他是一个带权无根树。首先把它以0为根看成有根树,对于给出的三个点,每两个点之间的距离是固定的,因为他们之间只有一条路,但是对于这么多查询(at most 70000 ),直接找距离代价太大,找出每两个点的LCA,这样就可以两个点之间的距离了,(需要知道从0点开始到这两个点的距离)。 我们把这三对点的距离加起来再除以2,就能得到连接着三个点的最短路径。

(更多…)

继续阅读 →