[codeforces 519E]E. A and B and Lecture Rooms(树上倍增)

题目:http://codeforces.com/problemset/problem/519/E

题意:给你一个n个点的树,有m个询问(x,y),对于每个询问回答树上有多少个点和x,y点的距离相等

分析:对于x,y,容易知道距离相等的点是链x->y上的中点除去x、y所在子树的其他所有子树的和

于是分类:

链x->y的长度是奇数:则一定没有距离相等的点,输出0

链x->y的长度是偶数:

  链上的中点Mid恰好是x,y的lca,则输出n-size[lca(x,y)的某个儿子(这个儿子是x的父亲)]-size[lca(x,y)的某个儿子(这个儿子是y的父亲)]

  链上的中点mid不是lca,那么必然在x->lca这条链上,那么输出size[mid]-size[x]

注意对于某个询问x=y的情况,此时输出n

原文地址:https://www.cnblogs.com/wmrv587/p/4364061.html