题意：给定一棵树，每次询问到达点u,v距离相等的点有多少个。
分析:按情况考虑：
1.abs(deep[u]-deep[v])%2==1时，必定不存在到达u,v距离相等的点。
2.如果deep[u]==deep[v]时，ans=n-num[lca(u,v)u在的儿子树]-num[lca(u,v)v在的儿子树]。
3.如果deep[u]!=deep[v]时，在u到v的路径中找出到达u,v相等的节点x，则ans=num[x]-num[u在的x儿子树].
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <map> #define N 200010 #define LL long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; struct edge { int v,next; edge() {} edge(int v,int next):v(v),next(next) {} } e[N]; int head[N],tot; int num[N],deep[N]; int fa[N][20]; void init() { memset(head,-1,sizeof(head)); tot=0; } void addedge(int u,int v) { e[tot]=edge(v,head[u]); head[u]=tot++; } void dfs(int x,int f) { for(int i=1; i<20; i++) { if(deep[x]<(1<<i))break; fa[x][i]=fa[fa[x][i-1]][i-1]; } for(int i=head[x]; ~i; i=e[i].next) { int v=e[i].v; if(v==f)continue; fa[v][0]=x; deep[v]=deep[x]+1; dfs(v,x); num[x]+=num[v]; } } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int t=deep[x]-deep[y]; for(int i=0; i<=19; i++) if((1<<i)&t)x=fa[x][i]; for(int i=19; i>=0; i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } if(x==y)return x; return fa[x][0]; } int main() { int n,m; while(scanf("%d",&n)>0) { init(); for(int i=1; i<n; i++) { int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } for(int i=1;i<=n;i++)num[i]=1; deep[1]=1; dfs(1,0); scanf("%d",&m); while(m--) { int x,y; scanf("%d%d", &x,&y); if(deep[x]<deep[y])swap(x,y); if((deep[x]-deep[y])&1) printf("0 "); else { int xy=lca(x, y),tx=x; int t=(deep[x]+deep[y]-2*deep[xy])/2-1; for(int i=0;i<20;i++)if(t&(1<<i))x=fa[x][i]; if(deep[tx]==deep[y]) { t=deep[y]-deep[xy]-1; for(int i=0;i<20;i++)if(t&(1<<i))y=fa[y][i]; printf("%d ",n-num[x]-num[y]); } else printf("%d ", num[fa[x][0]]-num[x]); } } } }