题意理解一颗n−1条主要边的树,然后增加了m条附加边.
我们只能删除一条主要边,一条附加边,一种边叫做主要边,一种边叫做附加边.
要求删除两条边后,这棵树不再是连通的.
我们需要统计,有多少种方案可以使得不连通,输出方案数.
算法解析
附加边到底有什么用处?
对于每一条连接x,y节点的(x,y),其实我们都可以认为这条边,连接了(x,y)这条路径上的所有点.
当没有了主要边的时候,其实附加边就是我们的主要边.
所以说,附加边(x,y),就是将树上x,y之间的路径上的每条主要边,都覆盖了一次.
因为当(x,y)路径上的任意一条主要边消失后,他都可以成为主要边,去维护连通性.
因此现在我们的问题模型转化了.
给定一个n−1条边的树,求每一条树边,被非树边覆盖了多少次
树边也就是主要边
非树边也就是附加边
那么这就是一个树上差分统计覆盖次数问题了.
每一条附加边,使得(x,y)节点的路径上,每一个节点的权值+1.
此时我们的问题,变成了如何统计方案数.
我们来好好地分类讨论一下主要边,身上的附加边.
1.主要边被覆盖了0次,即上面只有0条附加边.
我们发现删除完这条主要边后,随意删除一条附加边,我们都可以让树不连通.也就是m种方案.
只要删除(2,4)这条红边,那么随意一条附加边,都可以满足条件.
2.主要边覆盖1次,即上面只有一条附加边
我们发现删除完这条主要边后,我们只能删除这条主要边的附加边.也就是11种方案.
也就是删除咱们图上面的(3,7)红边,然后我们只能删除那条上面的紫色边.
3.主要边覆盖大于1次,即上面有多条附加边
我们发现,怎么删除,总能连通.于是0种方案.
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
struct node
{
int n,v;
} e[N*2];
int h[N],f[N][20],t,d[N],x,y,n,m,ans,date[N];
void add(int u,int v)
{
t++;
e[t].v=v;
e[t].n=h[u];
h[u]=t;
}
void dfs(int x,int fa)
{
d[x]=d[fa]+1;
f[x][0]=fa;
for (int i=1; (1<<i)<=d[x]; i++)
{
f[x][i]=f[f[x][i-1]][i-1];
}
for (int i=h[x]; i; i=e[i].n)
{
if (e[i].v!=fa)
{
dfs(e[i].v,x);
}
}
}
int lca(int x,int y) {
if (d[x] < d[y]) {
swap(x, y);
}
int h = d[x] - d[y], k = 0;
while (h) {
if (h & 1) {
x = f[x][k];
}
h >>= 1;
k++;
}
if (x == y) {
return x;
}
for (int k = 19; k >= 0; k--) {
if (f[x][k] != f[y][k]) {
x = f[x][k];
y = f[y][k];
}
}
return f[x][0];
}
void query(int u,int fa) {
for (int i = h[u]; i; i = e[i].n) {
int v = e[i].v;
if (v == fa) continue;
query(v, u);
date[u] += date[v];
if (date[v] == 0)
ans += m;
else if (date[v] == 1) ans++;
}
}
void update(int x,int y) {
date[x]++;
date[y]++;
date[lca(x, y)] -= 2;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, u, v; i < n; i++) {
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
dfs(1, 0);
for (int i = 1, u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
update(u, v);
}
query(1, 0);
printf("%d
",ans);
}