/*
给定n个点的树，在其中加入m条新边（称为非树边）
现在可以割断一条树边，一条非树边，使图分裂成两个联通块，请问有几种切割方式
对树边进行分情况讨论
如果树边不处在环中，则割断这条树边后可以割断任意条非树边
如果树边仅仅被一个环包含，则割断这条树边后只能割断一条非树边，即环中的那条非树边
如果树边被两个及以上环包含，就不可能有合法的切割方式
那么考虑如何计算树边被多少个环包含
显然每次加入一条非树边（x，y），x->lca(x,y)->y->x就会形成一个环
如果第一次割断这个环上的边，那么第二次就必须割断（x，y）
注意这里的环仅仅指的是非树边沿着两段向上覆盖的环
那么每次加入一条非树边（x，y），就找到lca(x,y)，x->lca->y路径上的所有边权+1
如何将路径上所有边权+1：使用树上差分即可，仅仅操作lca，x，y三个点的权值即可
最后枚举每一条边，分类考虑边权=0,1,2的三种情况并求和即可
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
#define maxn 200005
struct Edge{
int to,nxt;}edge[maxn<<
1];
int head[maxn],tot,n,m,cnt[maxn];
void init(){
memset(head,-
1,
sizeof head);
tot=
0;
}
void addedge(
int u,
int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++
;
}
int f[maxn][
30],d[maxn],t;
void bfs(){
queue<
int>
q;
q.push(1);d[
1]=
1;
while(!
q.empty()){
int u=
q.front();q.pop();
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
int v=
edge[i].to;
if(d[v])
continue;
f[v][0]=
u;
d[v]=d[u]+
1;
for(
int k=
1;k<=
29;k++
)
f[v][k]=f[f[v][k-
1]][k-
1];
q.push(v);
}
}
}
int lca(
int x,
int y){
if(d[x]<
d[y])swap(x,y);
for(
int i=
29;i>=
0;i--
)
if(d[f[x][i]]>=d[y])x=
f[x][i];
if(x==y)
return y;
for(
int i=
29;i>=
0;i--
)
if(f[x][i]!=f[y][i])x=f[x][i],y=
f[y][i];
return f[x][
0];
}
long long ans;
void dfs(
int u,
int pre){
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
int v=
edge[i].to;
if(v==pre)
continue;
dfs(v,u);
cnt[u]+=
cnt[v];
}
}
int main(){
init();
cin>>n>>
m;
for(
int i=
1;i<n;i++
){
int u,v;
scanf("%d%d",&u,&
v);
addedge(u,v);addedge(v,u);
}
bfs();
for(
int i=
1;i<=m;i++
){
int u,v;
scanf("%d%d",&u,&
v);
cnt[lca(u,v)]-=
2;
cnt[u]++;cnt[v]++
;
}
dfs(1,
0);
for(
int i=
2;i<=n;i++
)
if(cnt[i]==
0)ans+=
m;
else if(cnt[i]==
1)ans++
;
cout<<ans<<
endl;
}
转载于:https://www.cnblogs.com/zsben991126/p/10511058.html
相关资源：各显卡算力对照表！
