题目描述

给定一颗树，其上全为主要边。

之后在上面任意节点连接附加边。

斩断一条主要边和一条附加边，使此图不连通。

样例

4 1
1 2
2 3
1 4
3 4

可见，一个环上的边，只要砍掉红颜色的树边，

砍掉其上任意一条黑色树边都是一种方案。

如果对应一条不在环上的点，则只用砍一条黑树边，然后砍任意一条红树边都为一种方案。

如果一个边同时在多条环上，则砍掉这条边后，还是有环，因为对于它组成的子图，

边数显然是大于无环时的边数的。

算法1

(树上差分 $+ LCA$) $O(nlog(n))$

说一下是怎么想到的，

首先由上面的分析知道，我们需要统计的是一条边在多少个环内，对于一条黑边有：

• $l = 0 : + m$
• $l = 1 : + 1$
• $l > 1 : + 0$

因为我们知道一条红边所连的点必是在一个环中的，由此可以推断出 $l$ 需要加 $1$ 的链，

由此想到了树上差分。

又由于树上差分需要求 $LCA$，故得出结论，

由于 $LCA$ 算法分为 预处理 和 在线处理 两部分。

运用了 倍增 的思想，

由于我们 所到的点 的各个决策都是不同的，可以将 不同的点 看作 不同的层。

由倍增可知，每一层有 $log(n)$ 个决策。

如果可以 $O(1)$ 转化不同的决策（未必是同层转化），就可以解决了。

int depth[N], fa[N][17];    // 数据在 2^17 以内

void bfs()
{
    queue<int> q;
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1; // 每个点所在的树的深度

    q.push(1);
    while (q.size())            // 由上往下更新，可以确定边界
    {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)    // 因为加的是无向边，但只能更新子节点
            {
                depth[j] = depth[t] + 1;    // 更新深度，以便于继续更新之后的节点。
                fa[j][0] = t;               // 往上走 1 步，为父节点，省掉了 ‘不走的’ 空间
                q.push(j);                  // 由上往下，继续更新其子节点
                for (int k = 1; k <= 16; k ++ ) // 当前层的所有决策
                    fa[j][k] = fa[fa[j][k - 1]][k - 1]; // 由之前层来更新，存的是能到哪个点
            }
        }
    }
}

然后就是在两个不同层根据不同的转移到达 $LCA$ 点，

如果分别枚举决策，由乘法原理可知，会有 $17!^2$ 种不同决策，

但我们有树的深度，这个限制条件，所以剪去大于条件者，并逐渐收敛，至 $17^2$ 种不同决策，

通常取用一个点代跑来判断，

$LCA$ 点的深度肯定是一样的，要是两个层深度一样，则转移的步数相同，

可以减少到 $17$ 种决策。

所以我们只需要将一个层深度执到与另一层深度相同时所在的点（由上分析知，只有 $17$ 种决策）

注意，我们判断不大于时，只能靠决策给出的点，但等于和大于二者都是相同的，

所以，暂取到等于减一，亦可，

int lca(int x, int y)
{
    // 确保 x 更深
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 16; k >= 0; k -- )
        if (depth[fa[x][k]] >= depth[y])
        {
            x = fa[x][k];
        }
    if (x == y) return y;
    for (int k = 16; k >= 0; k -- )
        if (fa[x][k] != fa[y][k])   // 为了便于判断不大于的条件，如此做所在点不同，最终为等于减一
        {
            x = fa[x][k];
            y = fa[y][k];
        }
    return fa[x][0]; // 返回此时 x 的父节点，等于减一加一 = 等于
}

/*
本题的要求是，砍掉一条主边和一条附加边，断开这个图
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

int n, m, ans;
int e[N], ne[N], h[N], idx;

int st[N], d[N];            // 每个点被覆盖的次数
int depth[N], fa[N][17];    // 数据在 2^17 以内

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs()
{
    queue<int> q;
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;

    q.push(1);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)    // 当前点过深, 也就是没有更新过
            {
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                q.push(j);                  // 一点要记得用它来更新其它点
                for (int k = 1; k <= 16; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int x, int y)
{
    // 确保 x 更深
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 16; k >= 0; k -- )
        if (depth[fa[x][k]] >= depth[y])
        {
            x = fa[x][k];
        }
    if (x == y) return y;
    for (int k = 16; k >= 0; k -- )
        if (fa[x][k] != fa[y][k])
        {
            x = fa[x][k];
            y = fa[y][k];
        }
    return fa[x][0]; // 返回此时 x 的父节点
}

void dfs(int u)
{
    st[u] = 1;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            dfs(j);

            if (d[j] == 0) ans += m;
            else if (d[j] == 1) ans ++ ;
            d[u] += d[j];
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m);

    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b), add(b, a);
    }

    bfs();
    for (int i = 1; i <= m; i ++ )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        int p = lca(a, b);
        d[a] ++, d[b] ++, d[p] -= 2;
    }

    dfs(1);
    printf("%d", ans);
    return 0;
}