A and B and Lecture Rooms

题意

题目的意思就是每次询问点x，y，要你求其中离它们距离一样的点有多少个。

分析

我们可以先找到这两个点的 ，然后路径的中点肯定是一个解（没有就无解咯）。然后从这个点不经过 这条路径任意一点能到达的点，就是其他解。
求法的话，比较两个询问节点的深度

深度相同：

深度不同：

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e5+5,INF=0x3f3f3f3f;
using namespace std;

int head[N],size[N],dep[N],fa[N][15];
int n,cnt,m;
struct node
{
    int to,nxt;
}e[N<<1];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

void add(int x,int y)
{
    e[++cnt].to=y;
    e[cnt].nxt=head[x];
    head[x]=cnt;
}

void dfs(int x,int fath)
{
    size[x]=1,dep[x]=dep[fath]+1,fa[x][0]=fath;
    for(int i=1;i<14;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=e[i].nxt)
    {
        if(e[i].to==fath) continue;
        dfs(e[i].to,x);
        size[x]+=size[e[i].to];
    }
}

void getans(int x,int y)
{
    if(x==y)
    {
        printf("%d\n",size[1]);
        return;
    }
    if(dep[x]==dep[y])
    {
        for(int i=14;i>=0;i--)
            if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
        printf("%d\n",size[1]-size[x]-size[y]);
        return;
    }
    if(dep[x]<dep[y]) swap(x,y);
    if((dep[x]-dep[y])&1)
    {
        printf("0\n");
        return;
    }
    int x1=x,d=(dep[x]-dep[y])>>1;
    for(int i=13;i>=0;i--)
        if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y)
    {
        d=dep[x]+d;
        for(int i=13;i>=0;i--)
            if(dep[fa[x1][i]]>d)
                x1=fa[x1][i];
        printf("%d\n",size[fa[x1][0]]-size[x1]);
        return;
    }
    for(int i=13;i>=0;i--)
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    d=dep[x]-1+d;
    for(int i=13;i>=0;i--)
     if(dep[fa[x1][i]]>d) x1=fa[x1][i];
    printf("%d\n",size[fa[x1][0]]-size[x1]);
}

int main()
{  
    n=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    dfs(1,1);
    m=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        getans(x,y);
    }
    return 0;
}