A and B and Lecture Rooms

这题的思维难度并不很大

但是细节有一点点需要注意

首先两点间的距离如果是奇数必定无解

如果是偶数,那么可以找到中间的那个点,必定满足条件

而且从延伸出去的各种分支,只要不是包含的分枝都是满足条件的

因为两点都是从拐过去的

这个规律在任意时刻都是适用的

但是当deep[l]==deep[r]注意一下计算方式

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5+10; 
int n;
struct edge{
    int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){
    d[++cnt] = (edge){v,head[u]},head[u] = cnt;
}
int fa[maxn][20],deep[maxn],siz[maxn];
void dfs(int u,int faa)
{
    fa[u][0] = faa, deep[u] = deep[faa]+1; siz[u] = 1;
    for(int i=1;i<=18;i++)
        fa[u][i] = fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v==faa )    continue;
        dfs(v,u);
        siz[u] += siz[v];
    }
}
int X,Y;
int lca(int x,int y)
{
    if( deep[x]<deep[y] )    swap(x,y);
    for(int i=18;i>=0;i--)
        if( deep[fa[x][i]]>=deep[y] )    x = fa[x][i];
    if( x==y )    return x;
    for(int i=18;i>=0;i--)
        if( fa[x][i]!=fa[y][i] )
            x=fa[x][i], y = fa[y][i];
    X=x,Y=y;
    return fa[x][0];
}
int k_th(int x,int depth)
{
    for(int i=18;i>=0;i--)
        if( depth&(1<<i) )    x=fa[x][i];
    return x;
}
int dis(int l,int r,int ff){
    return deep[l]+deep[r]-2*deep[ff];
}
int main()
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        int l,r; scanf("%d%d",&l,&r);
        add(l,r); add(r,l);
    }
    deep[0]=-1; dfs(1,0);
    int q; cin >> q;
    while( q-- )
    {
        int l,r; scanf("%d%d",&l,&r);
        int ff = lca(l,r);
        int juli = dis(l,r,ff);
        if( l==r )    cout << n << endl;
        else if( juli%2==1 )    cout << 0 << endl;
        else
        {
            if( deep[l]==deep[r] )
            {
                int nxtl=nxt_th(l,juli/2),nxtr=nxt_th(r,juli/2);
                cout << n-siz[nxtl]-siz[nxtr] << endl;
                continue;
            }
            int mid,nxt,kl;
            if( deep[l]>deep[r] )
                mid = k_th(l,juli/2),nxt=k_th(l,juli/2-1);
            else
                mid = k_th(r,juli/2),nxt=k_th(r,juli/2-1);
            cout << siz[mid]-siz[nxt] << endl;
        }
    }
}