题目大意

给出一张$n$个点$m$条边的无向图$G$，其中有$n-1$条“主要边”，保证任意两点有且仅有一条简单路径。同时有若干条“附属边”。要求切断一条“主要边”，一条“附属边”，使得$G$不连通。

数据范围

$n\le 10^5,m\le 2\times 10^5$

思路

记$n-1$条“主要边”构成的树为$T$。

对于每一条主要边$\langle u,v\rangle$，如果没有“附属边”，如果删去其必然会分成两个连通块，而如果分成的连个连通块$G_1$,$G_2$任意两点存在一条边，那么仍然为一棵树。

如果存在一条以上的边，那么显然无解。

那么我们考虑如何计算删掉每条“主要边”后，其分成的两个连通块间的“附属边”条数$k$。

对于每条“附属边”$\langle x,y\rangle$，显然删掉在$T$上路径$(x,y)$上的任意一条边，都可以保证$G$连通，即删掉在路径$(x,y)$上的任一条“主要边”$\langle u,v\rangle$，其分成的两个连通块$G_1$,$G_2$都存在一条$\langle x,y\rangle$,因此删掉$(x,y)$上的任意一条边后，要确保图$G$不连通，则必须删掉附属边$\langle x,y\rangle$。

那么我们称“附属边”$\langle x,y\rangle$覆盖了$(x,y)$上的所有“主要边”，需要将这些边的$k_i+1$。

那么就可以直接进行树上差分了。

#include <iostream>
#include <cstring>

namespace wxy{
    const int N = 1e5 + 10,M = 2e5 + 10;
    int head[N],edge[N << 1],fail[N << 1],val[N],tot;
    int d[N],fa[N][30];
    int n,m;
    bool vis[N];
    inline void add(int x,int y){
        edge[++tot] = y;
        fail[tot] = head[x];
        head[x] = tot;
    }
    void dfs_table(int u){
        vis[u] = true;
        for (int i = 1;(1 << i) <= n; i++)
            fa[u][i] = fa[fa[u][i-1]][i-1];
        for (int i = head[u];i;i = fail[i]){
            int v = edge[i];
            if (vis[v]) continue;
            d[v] = d[u] + 1;
            fa[v][0] = u;
            dfs_table(v);
        }
    }
    void dfs_val(int u){
        vis[u] = true;
        for (int i = head[u]; i; i = fail[i]){
            int v = edge[i];
            if (vis[v]) continue;
            dfs_val(v);
            val[u] += val[v];
        }
    }
    inline int lca(int x,int y){
        if (d[x] < d[y]) std::swap(x,y);
        int i,j;
        for (i = 0; (1 << i) <= n; i++);
        for (j = i;j >= 0; j--){
            if (d[fa[x][j]] >= d[y]) x = fa[x][j];
        }
        if (x == y) return x;
        for (j = i;j >= 0; j--){
            if (fa[x][j] != fa[y][j]){
                x = fa[x][j];
                y = fa[y][j];
            }
        }
        return fa[x][0];
    }
    inline void flip(int u,int v){
        val[u]++;
        val[v]++;
        val[lca(u,v)] -= 2;
    }
    void main(){
        std::cin >> n >> m;
        memset(d,-1,sizeof d);
        d[1] = 0;
        for (int i = 1; i < n; i++){
            int a,b;
            std::cin >> a >> b;
            add(a,b);
            add(b,a);
        }
        dfs_table(1);
        for (int i = 1; i <= m; i++){
            int a,b;
            std::cin >> a >> b;
            flip(a,b);
        }
        memset(vis,false,sizeof vis);
        dfs_val(1);
        int ans = 0;
        for (int i = 2; i <= n; i++){
            if (val[i] > 1) continue;
            if (val[i] == 0) ans += m;
            else ans++;
        }
        std::cout << ans;
    }
}signed main(){wxy::main();return 0;}