题目描述
给定一颗树,其上全为主要边。
之后在上面任意节点连接附加边。
斩断一条主要边和一条附加边,使此图不连通。
样例
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$ 的链,
由此想到了树上差分。
/*
本题的要求是,砍掉一条主边和一条附加边,断开这个图
*/
#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;
}