519e专题

A and B and Lecture Rooms CodeForces - 519E(LCA倍增,思维)

题目大意 给定一棵树,然后q个询问,距离两个点距离相等点的个数。 思路 先用LCA求出两个点的最近公共祖先,然后判断距离,如果说两个点距离lca的距离和为奇数那么不存在距离相等的点,如果说距离为偶数,那么又可以分出两种情况,第一种情况是距离相等那么就是所有的点数量去掉包lca包含a,b子树的节点数。距离不相等,那么就是中点位置的子树节点数减去其包含深度大的那个结点子树。 代码 #incl