题意：她想知道树上所有节点到该路径的最短路之和是多少

题解：LCA(用于求两个点之间的距离)+换根DP(求每个点为根，其他点到根的距离)

ans=(dp[x]+dp[y]-n*dist(x,y))/2

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
#define fi first
#define se second
#define int long long
/*
    第一遍dfs，搞出fa，dep，son数组
    第二遍dfs，算出tp数组
    让两个游遍沿着各自的重链向上跳，跳到同一条重链上时，
        深度较小的那个游标所指向的点就是LCA
*/
int n,m,q;
vector<int> g[N];
int fa[N],dep[N],son[N],sz[N];
int tp[N];
void dfs1(int u,int father)
{
    fa[u]=father;   dep[u]=dep[father]+1;   sz[u]=1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==father)   continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        //哪个子树节点个数大则谁为重儿子
        if(sz[son[u]]<sz[v])    son[u]=v;
    }
}

//先一直找重链，然后处理轻链
void dfs2(int u,int t)
{
    tp[u]=t;    //记录链头
    if(!son[u]) return ;    //如果无重儿子则返回
    dfs2(son[u],t); //搜重儿子
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==fa[u]||v==son[u]) continue;   //如果当前点为父亲节点或者为链头
        dfs2(v,v);  //搜轻儿子
    }
}

int dp[N];
void dfs(int u,int father)
{
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==father)    continue;
        dp[v]=(dp[u]-sz[v])+(n-sz[v]);
        dfs(v,u);
    }
}
int lca(int u,int v)
{
    while(tp[u]!=tp[v])
    {
        if(dep[tp[u]]<dep[tp[v]]) swap(u,v);
        u=fa[tp[u]];
    }
    return dep[u]<dep[v]?u:v;
}
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=n-1;i++)
    {
        int x,y;    cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    
    dfs1(1,-1);
    dfs2(1,1);
    for(int i=1;i<=n;i++)   dp[1]+=dep[i];
    dp[1]-=n;

    dfs(1,-1);
    while(q--)
    {
        int x,y;    cin >> x >> y;
        int lc=lca(x,y);
        int dist=dep[x]-dep[lc]+dep[y]-dep[lc];
        cout << (dp[x]+dp[y]-n*dist)/2 << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin >> T;
    while(T--)
        solve();
}