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