思路与算法

一个只含一条给定树边的割，必须把该边两侧整棵子树分开。该割大小为1加跨过这条树边的非树边条数。对每条非树边(u,v)做d[u]++、d[v]++、d[LCA]-=2，后序累加得到各父边覆盖数，取最小值加1。

正确性说明

删掉指定树边得到唯一二分；若割中不再删其他树边，其余树边保证两侧各自连通，因此不能选其他二分。非树边跨割当且仅当其树路径包含指定边。边差分在共同祖先处抵消，后序和正好统计各父边路径次数，故最小值满足限制。

复杂度

建树遍历O(n)，倍增预处理O(nlogn)，非树边LCA O(mlogn)，后序O(n)，空间O(nlogn+m)宽松上界；非树边逐条读入，不必保存。

易错点

必须使用边差分的两倍LCA修正，不是点差分。只查询非根父边，不能把根的0覆盖当作答案。题目给定的树是原图的生成树，前n-1行不能与其他边混淆。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> g(n);
        for (int i = 1, u, v; i < n; i++) {
            cin >> u >> v;
            --u;
            --v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int LG = 1;
        while ((1 << LG) <= n)
            LG++;
        vector<vector<int>> up(LG, vector<int>(n));
        vector<int> dep(n), ord(1, 0), d(n);
        for (int i = 0; i < n; i++) {
            int u = ord[i];
            for (int v : g[u])
                if (v != up[0][u]) {
                    up[0][v] = u;
                    dep[v] = dep[u] + 1;
                    ord.push_back(v);
                }
        }
        for (int j = 1; j < LG; j++)
            for (int i = 0; i < n; i++)
                up[j][i] = up[j - 1][up[j - 1][i]];
        auto lca = [&](int u, int v) {
            if (dep[u] < dep[v])
                swap(u, v);
            for (int j = LG - 1; j >= 0; j--)
                if (dep[u] - (1 << j) >= dep[v])
                    u = up[j][u];
            if (u == v)
                return u;
            for (int j = LG - 1; j >= 0; j--)
                if (up[j][u] != up[j][v]) {
                    u = up[j][u];
                    v = up[j][v];
                }
            return up[0][u];
        };
        for (int i = n - 1, u, v; i < m; i++) {
            cin >> u >> v;
            --u;
            --v;
            d[u]++;
            d[v]++;
            d[lca(u, v)] -= 2;
        }
        int ans = m + 1;
        for (int i = n - 1; i > 0; i--) {
            int u = ord[i];
            ans = min(ans, d[u] + 1);
            d[up[0][u]] += d[u];
        }
        cout << ans << '\n';
    }
}