题目描述

本题和$hard$难度的区别是，询问的次数有多次！

小红拿到了一棵树，她有多次询问，每次询问输入一条简单路径$x,y$，她想知道树上所有节点到该路径的最短路之和是多少，你能帮帮她吗？

定义节点到路径的最短路为：节点到路径上所有点的最短路中，值最小的那个。特殊的，如果节点在路径上，则最短路为0。

简单路径：从树上的一个节点出发，沿着树的边走，不重复地经过树上的节点，到达另一个节点的路径。

第一行输入两个正整数$n,q$，代表节点数量和询问次数。
接下来的$n-1$行，每行输入两个正整数$u,v$，代表节点$u$和节点$v$有一条边连接。
接下来的$q$行，每行输入两个正整数$x,y$，代表一次询问。
$1\leq n,q \leq 10^5$
$1\leq u,v,x,y \leq n$

输入

4 2
1 2
1 3
1 4
2 3
2 1

输出

1
2

实现

​

​ 并没有看懂关于所有点到链的距离和即所有点到左右端点的距离和加上链长的证明，但有了这个结论就比较好写了，比较板的换根dp求距离和加上倍增lca求链长。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6 + 10;
const int M = 5e3 + 10;
vector<int>e[N];
int V[N],f[N],Size[N];
bool st[N];
int dep[N],fa[N],par[N][33];
void up(int u){
    Size[u]=1;
    st[u]=1;
    for(int v:e[u]){
        if(st[v]) continue;
        fa[v]=u;
        par[v][0]=u;
        up(v);
        Size[u]+=Size[v];
        f[u]+=f[v];
    }
    f[u]+=Size[u]-1;
    st[u]=0;
}
void down(int u){
    st[u]=1;
    for(int v:e[u]){
        if(st[v]) continue;
        dep[v]=dep[u]+1;
        V[v]=V[u]+f[u]-f[v]+Size[1]-Size[v]-Size[v];
        down(v);
    }
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    while(dep[u]!=dep[v]){
        u=fa[u];
    }
    int d=dep[u]-dep[v];
    if(u==v) return u;
    for(int j=20;j>=0;j--){
        if(par[u][j]!=par[v][j]){
            u=par[u][j];
            v=par[v][j];
        }
    }
   return par[u][0];
}
void solve()
{   
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[1]=1;
    up(1);
    down(1);
    for(int i=1;i<=21;i++){
        for(int j=1;j<=n;j++){
            if(par[j][i-1]!=0)
            par[j][i]=par[par[j][i-1]][i-1];
        }
    }
    for(int i=1;i<=q;i++){
        int u,v;
        cin>>u>>v;
        int dist1=V[u]+f[u];
        int dist2=V[v]+f[v];
        int dist3=dep[u]+dep[v]-2*dep[lca(u,v)];
        cout<<(dist1+dist2-n*dist3)/2<<endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
}