思路与算法

主要边构成树。先统计每条主要边被多少条附加边跨越：对附加边(u,v)，给u、v各加1，给LCA(u,v)减2，再按逆序把差分值累加到父节点。每个非根节点的累加值就是父边的覆盖数c。逐条主要边计数：c=0时贡献M，c=1时贡献1，c≥2时贡献0。

正确性说明

删掉一条主要边后，树分成两块，只有跨越这两块的附加边能够继续连接它们。若跨越数为0，第一刀已断开，第二刀仍必须选择任意一条附加边，所以有M种；若只有1条，第二刀只能删掉它；若至少2条，再删1条仍连通。树上边差分恰好让每条附加边在其对应树路径上贡献1，所以覆盖数和最后的方案数都正确。

复杂度

倍增预处理与M次LCA合计 O((N+M) log N)，逆序累加 O(N)，空间 O(N log N)。

易错点

覆盖数为0时也必须执行第二刀，不能只贡献1。附加边可能重合，也可能两端相同，按独立的附加边计数；同点路径对树边无贡献。用迭代遍历生成逆序，避免10万点长链递归过深。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    const int K = 18;
    vector<array<int, K>> up(n);
    vector<int> depth(n), order(1, 0), parent(n, -1), delta(n);
    parent[0] = 0;
    for (size_t at = 0; at < order.size(); at++) {
        int u = order[at];
        for (int v : g[u])
            if (v != parent[u]) {
                parent[v] = u;
                depth[v] = depth[u] + 1;
                order.push_back(v);
            }
    }
    for (int v : order) {
        up[v][0] = parent[v];
        for (int k = 1; k < K; k++)
            up[v][k] = up[up[v][k - 1]][k - 1];
    }
    auto lca = [&](int u, int v) {
        if (depth[u] < depth[v])
            swap(u, v);
        int difference = depth[u] - depth[v];
        for (int k = 0; k < K; k++)
            if (difference >> k & 1)
                u = up[u][k];
        if (u == v)
            return u;
        for (int k = K - 1; k >= 0; k--)
            if (up[u][k] != up[v][k]) {
                u = up[u][k];
                v = up[v][k];
            }
        return parent[u];
    };
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        int w = lca(u, v);
        delta[u]++;
        delta[v]++;
        delta[w] -= 2;
    }
    long long ans = 0;
    for (int i = n - 1; i > 0; i--) {
        int v = order[i];
        if (delta[v] == 0)
            ans += m;
        else if (delta[v] == 1)
            ans++;
        delta[parent[v]] += delta[v];
    }
    cout << ans << '\n';
}