题意：
给你一棵有n个节点的树，给你m次询问，查询给两个点，问树上有多少个点到这两个点的距离是相等的。树上所有边的边权是1。
思路：
很容易想到通过记录dep和找到lca来找到两个点之间的距离，然后分情况讨论。
一开始困扰我的问题是如果lca不是正中间的点，如何在比较低的复杂度的层面上求解中点。
倍增法lca不光可以在logn的时间复杂度内查询某两个点的lca，还可以实现在logm的时间复杂度能查询某个节点的第m个父亲节点。
算法的核心是用二进制的运算来实现查询。
#include<bits/stdc++.h>
#define N 100050
using namespace std;
int n;
struct edge{
int id;
edge *next;
};
edge edges[N<<];
edge *adj[N];
int ednum;
int dep[N],rt[][N],siz[N];
inline void add_Edge(int a,int b){
edge *tmp=&edges[ednum++];
tmp->id=b;
tmp->next=adj[a];
adj[a]=tmp;
}
void dfs(int pos,int deep){
dep[pos]=deep;
siz[pos]=;
for(edge *it=adj[pos];it;it=it->next){
if(!dep[it->id]){
rt[][it->id]=pos;
dfs(it->id,deep+);
siz[pos]+=siz[it->id];
}
}
}
void prelca(){
for(int i=;i<=;i++){
for(int j=;j<=n;j++){
rt[i][j]=rt[i-][j]==-?-:rt[i-][rt[i-][j]];
}
}
}
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=;i<;i++){
if((dep[u]-dep[v])>>i&){
u=rt[i][u];
}
}
if(u==v)return u;
for(int i=;i>=;i--){
if(rt[i][u]!=rt[i][v]){
u=rt[i][u];
v=rt[i][v];
}
}
return rt[][u];
}
int jump(int pos,int num){
for(int i=;i<;i++){
if(num>>i&){
pos=rt[i][pos];
}
}
return pos;
}
void solve(int u,int v){
if(u==v){
printf("%d\n",n);
return;
}
if(max(dep[u],dep[v])-min(dep[u],dep[v])&){
printf("0\n");
return;
}
int anc=LCA(u,v);
//printf("anc=%d\n",anc);
if(dep[u]==dep[v]){
int ans=n;
ans-=siz[jump(u,dep[u]-dep[anc]-)];
ans-=siz[jump(v,dep[u]-dep[anc]-)];
printf("%d\n",ans);
}
else{
int l=dep[u]+dep[v]-*dep[anc];
if(dep[u]<dep[v])swap(u,v);
int ans=siz[jump(u,l/)];
ans-=siz[jump(u,l/-)];
printf("%d\n",ans);
}
}
int main()
{
scanf("%d",&n);
memset(rt,-,sizeof(rt));
for(int i=;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
add_Edge(a,b);
add_Edge(b,a);
}
dfs(,);
prelca();
//printf("*%d\n",jump(2,0));
int m;
scanf("%d",&m);
for(int i=;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
solve(a,b);
}
return ;
}
/*
5
1 5
1 2
2 3
2 4
5
1 5
2 5
1 1
2 2
3 4
*/