题意
传送门 POJ 3417 Network
题解
在树上新增边 ( x , y ) (x,y) (x,y) 会出现环,称构成的环上的树边,即 x x x 到 y y y 的路径被新增边覆盖了 1 1 1 次。若树上某条边被新增边覆盖次数为 0 0 0,即这条边不经过环,那么可以任取 M M M 条新增中的一条破坏;若树上某条边被新增边覆盖次数为 1 1 1,那么这条边恰好经过一个环,那么破坏方案只有一种;若树上某条边被新增边覆盖次数为 2 2 2,不存在破坏方案。
统计原来树上的边被新增边覆盖次数,使用树上差分求解,将边用端点中属于儿子的节点表示,设覆盖次数为
c
h
ch
ch,那么对于边
x
,
y
x,y
x,y
c
h
[
x
]
=
c
h
[
x
]
+
1
,
c
h
[
y
]
=
c
h
[
y
]
+
1
,
c
h
[
l
c
a
(
x
,
y
)
]
=
c
h
[
l
c
a
(
x
,
y
)
]
−
2
ch[x]=ch[x]+1,ch[y]=ch[y]+1,ch[lca(x,y)]=ch[lca(x,y)]-2
ch[x]=ch[x]+1,ch[y]=ch[y]+1,ch[lca(x,y)]=ch[lca(x,y)]−2 最后对树进行一次
D
F
S
DFS
DFS 就可以统计出
x
x
x 与其父节点的连边被覆盖的次数,同时统计答案即可。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 100005
#define maxlg 17
typedef long long ll;
int N, M, ch[maxn], lg[maxn], fa[maxlg][maxn], dep[maxn];
int head[maxn], nxt[maxn << 1], to[maxn << 1], tot = 1;
void add(int x, int y)
{
to[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
void dfs(int x, int f, int d)
{
fa[0][x] = f, dep[x] = d;
for (int i = 1; i <= lg[d]; ++i)
fa[i][x] = fa[i - 1][fa[i - 1][x]];
for (int i = head[x]; i; i = nxt[i])
{
int y = to[i];
if (y != f)
dfs(y, x, d + 1);
}
}
int lca(int x, int y)
{
if (dep[x] < dep[y])
swap(x, y);
while (dep[x] > dep[y])
x = fa[lg[dep[x] - dep[y]]][x];
if (x == y)
return x;
for (int i = lg[dep[x]]; i >= 0; --i)
if (fa[i][x] != fa[i][y])
x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
void get_sum(int x, int f, ll &res)
{
for (int i = head[x]; i; i = nxt[i])
{
int y = to[i];
if (y != f)
{
get_sum(y, x, res);
res += ch[y] == 0 ? M : (ch[y] == 1 ? 1 : 0);
ch[x] += ch[y];
}
}
}
int main()
{
scanf("%d%d", &N, &M);
lg[0] = -1;
for (int i = 1; i < N; ++i)
lg[i] = lg[i - 1] + (1 << (lg[i - 1] + 1) == i);
for (int i = 1; i < N; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
dfs(1, 0, 0);
for (int i = 1; i <= M; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
++ch[x], ++ch[y], ch[lca(x, y)] -= 2;
}
ll res = 0;
get_sum(1, 0, res);
printf("%lld", res);
return 0;
}