题目链接

https://vjudge.net/problem/CodeForces-519E

解题思路

整体思路：LCA

详细思路：

前置知识： 里面的链接是知识点的讲解

具体思路：

我们分两种大情况

  • u==LCA(u,v) || v==LCA(u,v)

    小情况1：若u==v，则答案直接就是n；
    小情况2：若u！=v，会出现如图情况：
    图片说明
    显然，绿色的节点是满足题意的节点，总结而言，先找到处于u，v中间深度的节点，用以这个节点为根的子树包含的节点数减去以“u所在路径上这个节点的直接子节点”为根的子树包含的节点数，即为答案。

  • u!=LCA(u,v) && v!=LCA(u,v)

    这种大情况，相当于u，v的路径跨越了它们的LCA节点。
    小情况1：若deep[u]==dp[v]，即u，v的深度相同，还是画图形象：
    图片说明
    就挺形象吧，我还真不知道怎么描述好，这一画图直接明明白白的。
    对于这种情况，总结而言，先找到u所在路径的lca的直接子节点，记为x，v所在路径的lca的直接子节点，记为y（在本图中x，y分别为u，v的直接父亲节点），用全部节点数n-以x为根的子树包含的节点数-以y为根的子树包含的节点数。
    小情况2：若deep[u]!=dp[v]，即u，v的深度不相同，再来个图：
    图片说明
    答案为，先找到处于u，v路径中间位置的节点，用以此节点为根的树包含的节点数-以“u所在路径上的中间位置节点的直接儿子”为根的树包含的节点数。

小总结：

这些结论的得出其实不难，并不需要严谨的证明，多举几组样例就可以了。而且，对于这种题而言，我们要讨论的大情况无非就是两节点的相对位置，也就是在同一根树枝上，或者不在同一根树枝上，小情况可以慢慢整理样例得出。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;

int n,m,ans,u,v,cnt;
int dp[N],head[N],fa[N][20],lg[N],sumson[N];
struct edge{int v,next;}e[N<<1];

//快读、链式前向星加边、获取lg数值（相当于先预处理一下移位操作） 
inline int read(){int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch-'0');return x*f;}
inline void add(int u,int v){e[++cnt].v=v;e[cnt].next=head[u];head[u]=cnt;}
inline void getlg(){for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);}

//dfs对fa数组赋值、对dp数组赋值、对sumson数组赋值 
void dfs(int x,int fath)
{
    dp[x]=dp[fath]+1;
    fa[x][0]=fath;
    sumson[x]=1;
    for(int i=1;i<=lg[dp[x]];i++)
    fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=e[i].next)
    {
        int v=e[i].v;
        if(fath==v) continue;
        dfs(v,x);
        sumson[x]+=sumson[v];
    }
}

//倍增法求LCA 
int LCA(int u,int v)
{
    while(dp[u]>dp[v]) u=fa[u][lg[dp[u]-dp[v]]-1];
    if(u==v) return u;
    for(int i=lg[dp[u]];i>=0;i--)
    if(fa[u][i]!=fa[v][i])
    u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}

//寻找距离节点x为dis的祖先节点
int find(int x,int dis)
{
    for(int i=lg[dp[x]];i>=0;i--)
    {
        if(dis-(1<<i)<0) continue;
        x=fa[x][i];dis-=(1<<i);
    }
    return x;
}

int main()
{
    n=read();
    for(int i=1;i<n;i++) {u=read();v=read();add(u,v);add(v,u);}

    getlg();dfs(1,0);

    m=read();
    while(m--)
    {
        u=read();v=read();
        if(dp[u]<dp[v]) swap(u,v);//保证u节点的深度不小于v节点的深度 
        int lca=LCA(u,v),dis=dp[u]+dp[v]-dp[lca]-dp[lca];//求u与v之间的（最短）距离 
        if(dis&1) {puts("0");continue;}//距离为奇数，不存在一个节点满足题意 
        dis>>=1;//距离除以2，得到离u，v最近的满足题意的节点到u，v的距离 
        if(v==lca)//如果深度较浅的节点v是u，v的LCA时，说明u，v在同一条支路上 
        {
            if(u==v) ans=n;//特判，u，v重合，所有点都满足题意//不特判结果出错 
            else
            {
                int midson=find(u,dis-1);//找到在u所在路径上，离u，v最近的满足题意的节点的子节点
                ans=sumson[fa[midson][0]]-sumson[midson];//midson的父亲节点为根的树包含的节点数量与midson节点为根的树包含的节点数量之差 
            }
        }
        else
        {
            if(dp[u]==dp[v])//u，v的LCA即为离u，v最近的满足题意的节点 
            {
                int umidson=find(u,dis-1),vmidson=find(v,dis-1);//找到u，v所在路径上，u，v的LCA的子节点 
                ans=n-sumson[umidson]-sumson[vmidson]; 
            }
            else
            {
                int midson=find(u,dis-1);//u，v深度不相等 
                ans=sumson[fa[midson][0]]-sumson[midson];//与v==lca&&v!=u的输出表达式是一样的 
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

个人总结

没AC，一直wa3。
主要原因：情况大致分对，但是并不细致，且缺少特判。
不过find函数及思想实现的还不错（大佬勿喷QWQ）。
写了俩小时题解，不打算留个赞再走吗，大佬QWQ

REF

https://blog.nowcoder.net/n/c37b1e71192e452db937c212bdff939e
https://www.cnblogs.com/qixingzhi/p/9302038.html