A and B and Lecture Rooms

题意：
有一颗n个节点的树，有m个询问，每个询问给出x和y两个节点，让你求树上节点到这两个节点距离相等的数目。

思路：
①：如果x和y深度相同，则他们的最近公共祖先lca（x,y)的非这二个节点方向的节点以外的节点到x和y的距离相等.
②：如果x和深度不同，则他们的路径为奇数时无解，为偶数时中点在深度大的一方，该点到x和y的方向节点以外的节点到x和y的距离相等.

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

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

int n, q, parent[22][100005], dep[100005], se[100005];
vector<int> g[100005];

int dfs(int v,int d, int f)
{
    dep[v]=d;
    parent[0][v]=f;
    se[v]=1;
    for(int i=0; i<g[v].size(); i++)
    {
        if(g[v][i]!=f)
            se[v]+=dfs(g[v][i],d+1,v);
    }
    return se[v];
}

int lca(int u,int v)
{
    if(dep[u]<dep[v])
    {
        swap(u,v);
    }
    for(int i=21;i>=0;i--)
    {
        if((dep[u]-dep[v])>=(1<<i))
        {
            u=parent[i][u];
        }
    }
    if(u==v)
    {
        return u;
    }
    for(int i=21;i>=0;i--)
    {
        if(parent[i][u]!=parent[i][v])
        {
            u=parent[i][u];
            v=parent[i][v];
        }
    }
    return parent[0][u];
}

int shang(int v,int d)
{
    for(int i=21;i>=0;i--)
    {
        if((d>>i)&1)
        {
            v=parent[i][v];
        }
    }
    return v;
}

int fun(int x,int y)
{
    if(dep[x]==dep[y])
    {
        if(x==y)
        {
            return n;
        }
        int v=lca(x,y);
        int d=dep[x]-dep[v];
        return n-se[shang(x,d-1)]-se[shang(y,d-1)];
    }
    else
    {
        int v=lca(x,y);
        int dx=dep[x]-dep[v], dy=dep[y]-dep[v];
        if(dx>dy)
        {
            int d=dx-dy;
            if(d%2==0)
            {
                int ki=shang(x,dx-d/2-1);
                return se[parent[0][ki]]-se[ki];
            }
            else
            {
                return 0;
            }
        }
        else
        {
            int d=dy-dx;
            if(d%2==0)
            {
                int ki=shang(y,dy-d/2-1);
                return se[parent[0][ki]]-se[ki];
            }
            else
            {
                return 0;
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0; i<n-1; i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(parent,-1,sizeof(parent));
    dfs(1,0,-1);
    for(int i=1;i<21;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(parent[i-1][j]<1)
            {
                parent[i][j]=-1;
            }
            else
            {
                parent[i][j]=parent[i-1][parent[i-1][j]];
            }
        }
    }
    scanf("%d",&q);
    while(q--)
    {
        int x, y;
        scanf("%d%d",&x,&y);
        cout << fun(x,y) << endl;
    }
    return 0;
}