时间复杂度:(n+m)logn

void bfs() //预处理
{
    queue<int>q;
    q.push(1);
    d[1] = 1;
    while(q.size())
    {
        int x = q.front();
        q.pop();
        for(int i = head[x]; i ; i = next[i])
        {
            int y = ver[i];
            if(d[y]) continue;
            d[y] = d[x] + 1;
            dist[y] = dist[x] + edge[i];
            f[y][0] = x;
            for(int j = 1; j <= t; j ++ )
               f[y][j] = f[f[y][j-1]][j-1];
            q.push(y);
        }
    }
}

int lca(int x,int y)
{
    if(d[x] > d[y]) swap(x,y);
    for(int i = t; i >= 0; i --)
       if( d[f[y][i]] > d[x] ) y = f[y][i];
       if(x == y) return x;
    for(int i = t; i >= 0; i --)
       if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
    return f[x][0];
}

int main()
{
    t = (int)(log(n)/log(2))+1;
    bfs();
    for(int i = 1; i <= m; i ++ )
    {
        int x,y;
        cin>>x>>y;
        cout<<dist[x]+dist[y]-2*dist[lca(x,y)];
    }
}