思路与算法

对树边u→v，删边后u侧有s个点，首次到达v的期望步数为2s-1。以1为根，孩子u上行边权为2size[u]-1，下行边权为2(N-size[u])-1。预处理两类根前缀和与LCA，u到v的期望等于u上行到LCA再下行到v的两段和，最后取模。

正确性说明

由首次步条件期望或树的边往返计数，可推出穿过指定边前会在出发侧平均经过其每条内部边两次，最后跨边一次，因此为2(s-1)+1。树上到达目标必须依次首次穿过唯一路径各边，强马尔可夫性和期望线性使这些代价可相加；LCA分解精确。

复杂度

树读入、子树和前缀初始化O(N)，倍增表O(NlogN)，每次LCA O(logN)，总O((N+Q)logN)时间、O(NlogN)空间。期望实际为整数，64位求和后模1e9+7。

易错点

方向不同期望不同。u=v时0，N=1也支持；不要把无向树距离当作随机游走期望。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[--a].push_back(--b);
        g[b].push_back(a);
    }
    int K = 1;
    while ((1 << K) <= n)
        K++;
    vector<vector<int>> p(K, vector<int>(n));
    vector<int> dep(n, -1), sz(n, 1), ord(1, 0);
    vector<long long> up(n), dn(n);
    dep[0] = 0;
    for (size_t i = 0; i < ord.size(); i++) {
        int u = ord[i];
        for (int v : g[u])
            if (dep[v] < 0) {
                p[0][v] = u;
                dep[v] = dep[u] + 1;
                ord.push_back(v);
            }
    }
    for (int i = n - 1; i > 0; i--)
        sz[p[0][ord[i]]] += sz[ord[i]];
    for (int i = 1; i < n; i++) {
        int u = ord[i], v = p[0][u];
        up[u] = up[v] + 2LL * sz[u] - 1;
        dn[u] = dn[v] + 2LL * (n - sz[u]) - 1;
    }
    for (int k = 1; k < K; k++)
        for (int i = 0; i < n; i++)
            p[k][i] = p[k - 1][p[k - 1][i]];
    while (q--) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        int a = u, b = v;
        if (dep[a] < dep[b])
            swap(a, b);
        for (int k = K - 1; k >= 0; k--)
            if ((dep[a] - dep[b]) >> k & 1)
                a = p[k][a];
        if (a != b) {
            for (int k = K - 1; k >= 0; k--)
                if (p[k][a] != p[k][b]) {
                    a = p[k][a];
                    b = p[k][b];
                }
            a = p[0][a];
        }
        cout << (up[u] - up[a] + dn[v] - dn[a]) % MOD << '\n';
    }
}