最近公共祖先+前缀和

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct E{
    int nxt,to;
}e[N<<1];
int head[N],cnt,num[N],d[N],sum[N],f[N][25],n,m;
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
    num[u]++;
}
void dfs(int u,int fa){
    d[u]=d[fa]+1;f[u][0]=fa;sum[u]=sum[fa]+num[u];
    for(int i=1;(i<<i)<=d[u];i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
    }
}
int lca(int x,int y){
    if(d[x]<d[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if((1<<i)<=d[x]-d[y])
            x=f[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        add(u,v);add(v,u);
    }
    dfs(1,1);
    /*for(int i=1;i<=n;i++)
        cout<<num[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)
        cout<<sum[i]<<" ";
    cout<<endl;*/
    while(m--){
        int u,v;
        cin>>u>>v;
        int t=lca(u,v);
        cout<<sum[u]+sum[v]-2*sum[t]+num[t]<<'\n';
    }
    return 0;
}