A and B and Lecture Rooms

做法：lca

题意：

• 已知两点，求到这两点距离相同的点的个数

思路：

• 如果存在到这两点距离相同的点，那么这两点的距离一定是偶数
• 如果这两点的深度相同，那么他们向上走到他们最近的公共祖先的子节点，然后n减去以这两个点为根节点的子树大小
• 否则求减去这两个点的中点一下的部分

代码

// Problem: A and B and Lecture Rooms
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/110856
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m;
vector<int> g[N];

int lg[N],fa[N][25],depth[N],siz[N];

void init(){
    for(int i=1;i<=n;i++){
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
}

void dfs(int u,int father){
    fa[u][0]=father;
    depth[u]=depth[father]+1;
    siz[u]=1;
    for(int i=1;i<=lg[depth[u]];i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(auto v:g[u]){
        if(v==father) continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
}

int lca(int a,int b){
    if(depth[a]<depth[b]) swap(a,b);
    int k=depth[a]-depth[b];
    for(int i=lg[k];~i;i--){
        if((k>>i)&1) a=fa[a][i];
    }
    if(a==b) return a;
    for(int i=lg[depth[a]];~i;i--){
        if(fa[a][i]^fa[b][i]){
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}

int dis(int a,int b){
    return depth[a]+depth[b]-2*depth[lca(a,b)];
}

//x向上走k步
int up_pos(int x,int k){
    for(int i=lg[k];~i;i--){
        if((k>>i)&1) x=fa[x][i];
    }
    return x;
}

void solve(){
    cin>>n;
    init();
    rep(i,1,n-1){
        int u,v;cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,0);
    cin>>m;
    while(m--){
        int x,y;cin>>x>>y;
        int d=dis(x,y);
        if(d&1){
            cout<<"0\n";
            continue;
        }
        if(x==y){
            cout<<n<<"\n";
            continue;
        }
        int z=lca(x,y);
        if(depth[x]==depth[y]){
            int k=depth[x]-depth[z]-1;
            int xx=up_pos(x,k);
            int yy=up_pos(y,k);
            cout<<n-siz[xx]-siz[yy]<<"\n";
            continue;
        }
        if(depth[x]<depth[y]) swap(x,y);
        int x1=up_pos(x,d/2);
        int x2=up_pos(x,d/2-1);
        cout<<siz[x1]-siz[x2]<<"\n";
    }
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}