正解
主要边是原图的一棵生成树,附加边是图中的非树边。
对于每条非树边((x,y)),它会和树上(x)到(y)的路径构成一个环,当第一步切断(x)到(y)路径中的一条边时,第二步就需要切断非树边((x,y)),才能保证原图不联通。
但我们第二步只能切断一条边啊,所以如果第一步的路径对应的要切断两条或以上的非树边,就没有办法了。
所以我们枚举每条非树边((x,y)),把(x)到(y)路径上所有边的边权(+1),对于每条树边,如果边权为(0),则切断它之后原图已经不联通,第二条边随便切一条,共(m)种方案。如果边权为(1),则第二步必须切断对应的那条边,方案数(1),如果边权大于(2)则没有方案。
这个边权我们可以利用树上差分来维护,对于非树边((x,y)),令结点(x)和(y)的点权加(1),(lca(x,y))的点权减(2),这样每个点子树的点权和就是该点到它的父亲的边的边权。证明就不详细讲了。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
struct edge {
int to,nxt,w;
} e[N*5];
int n,m,head[N],cnt;
void add(int u,int v) {
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
int dep[N],f[N][25];
void build(int u,int fa) {
dep[u]=dep[fa]+1;
for(int i=1; (1<<i)<=dep[u]; i++) {
f[u][i]=f[f[u][i-1]][i-1];
}
for(int i=head[u]; i; i=e[i].nxt) {
int v=e[i].to;
if(fa==v) {
continue;
}
f[v][0]=u,build(v,u);
}
}
int lca(int x,int y) {
if(dep[x]<dep[y]) {
swap(x,y);
}
for(int i=22; i>=0; i--) {
if(dep[f[x][i]]>=dep[y]) {
x=f[x][i];
}
if(x==y) {
return x;
}
}
for(int i=22; i>=0; i--) {
if(f[x][i]^f[y][i]) {
x=f[x][i],y=f[y][i];
}
}
return f[x][0];
}
int diff[N],ff[N];
void dfs(int u,int fa) {
ff[u]+=diff[u];
for(int i=head[u]; i; i=e[i].nxt) {
int v=e[i].to;
if(fa==v) {
continue;
}
dfs(v,u),ff[u]+=ff[v];
}
}
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);
}
build(1,0);
for(int i=1,u,v; i<=m; i++) {
scanf("%d %d",&u,&v);
int tmp=lca(u,v);
diff[u]++,diff[v]++,diff[tmp]-=2;
}
dfs(1,0);
int ans=0;
for(int i=2; i<=n; i++) {
if(!ff[i]) {
ans+=m;
} else if(ff[i]==1) {
ans++;
}
}
printf("%d",ans);
return 0;
}