1. 题面
  2. 解题思路
  3. Code

题面

解题思路

倍增Lca

分析

首先，题目中给的是一颗无根树，将无根树转换为有根树处理，随便选一个点为根即可

到两点距离相等的点，应为两点之间唯一路径上的中点以及其延伸出去的点，如果两没有中点，则必不存在答案，特判即可

然后就是找中点的问题

具体实现起来会和 Lca 的位置有一定关系，所以需要求出 x、y 两点的 Lca，然后算出中点的距离

这样我们就可以找出两点的中点啦，这样答案即为中点及其延伸出的点的个数

但是仍然要分情况讨论（size[k] 为以 1 为根时 k 的子树大小）：

1、中点为 Lca 时，如询问 4、6

结果应该是手动红框框出来的辣些点，仔细研究一下，其实应该是 size[2]-size[3]-size[5]

也就是：中点的子树大小 − 路径上与中点相邻两个点的子树大小

2、中点不为 Lca ，询问的 x、y 都不是对方的祖先时，如询问 5、7

还是手动框出来的辣个点，ans=size[3]-size[4]

也就是： 中点的子树大小 − 与中点相邻且深度较大的点的子树大小

3、中点不为 Lca ，询问的 x、y 一方为对方的祖先时，如询问 1、7

不难发现，ans=size[3]-size[4]

和2中的结论一致，所以就讨论两种就好了

还要注意中点偏向 x 还是 y，操作的对象是不同的

如何求邻近点？

由于预处理了每个点的祖先情况，因此那些邻近点可以在知道距离的情况下用倍增求

Warning

可能存在查询的两点相同的情况，此时答案为 0

Code

#include<bits/stdc++.h>
#define rgt register
#define N 100003
using namespace std;
struct Edge{
    int to,nxt;
}b[N<<1];
int head[N],deep[N],size[N];
int n,T,dis,t,f[N][17],rx,ry,root;
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void add(rgt int x,rgt int y) {
    b[++t].to=y,b[t].nxt=head[x],head[x]=t;
    b[++t].to=x,b[t].nxt=head[y],head[y]=t;
}
inline void built(rgt int k,rgt int fa) {//处理倍增Lca
    rgt int    i,to;size[k]=1;
    deep[k]=deep[fa]+1;
    for(i=0;i<16;i++)//预处理出祖先情况
        f[k][i+1]=f[f[k][i]][i];
    for(i=head[k];i;i=b[i].nxt) {
        to=b[i].to;
        if(to==fa) continue;
        f[to][0]=k,built(to,k),size[k]+=size[to];
    }
}
inline int Lca(rgt int x,rgt int y) {//倍增求Lca
    if(deep[x]<deep[y]) swap(x,y);
    rgt int i;
    for(i=16;i>=0;i--) {
        if(deep[f[x][i]]>=deep[y])
            x=f[x][i];
        if(x==y) return x;
    }
    for(i=16;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
inline int getanc(rgt int res,rgt int k) {//倍增求res节点的k次祖先
    rgt int i,x;
    for(i=16,x=res;i>=0;i--)
        if(deep[res]-deep[f[x][i]]<=k)
            x=f[x][i];
    return x;
}
int main()
{
    int i,x,y;
    n=read();
    for(i=1;i<n;i++)
        x=read(),y=read(),add(x,y);
    built(1,0),T=read();
    while(T--) {
        x=read(),y=read();
        if(x==y) {printf("%d\n",n);continue;}//特判相等
        root=Lca(x,y);//求出Lca
        dis=deep[x]+deep[y]-deep[root]-deep[root];//就算两点间距离
        if(dis&1) {printf("0\n");continue;}//没有中点
        dis>>=1;//到路径中点的距离
        if(dis==deep[x]-deep[root]) {//Lca为中点的情况
            rx=getanc(x,dis-1),ry=getanc(y,dis-1);
            printf("%d\n",n-size[rx]-size[ry]);
        }
        else {
            if(dis<deep[x]-deep[root]) {//看中点偏向哪一边
                root=getanc(x,dis),rx=getanc(x,dis-1);
                printf("%d\n",size[root]-size[rx]);
            }//也就是看中点是x还是y的祖先，用dis判断比较方便
            else {
                root=getanc(y,dis),ry=getanc(y,dis-1);
                printf("%d\n",size[root]-size[ry]);
            }
        }
    }
    return 0;
}

devil.