题目描述
传说中的暗之连锁被人们称为 Dark。
Dark 是人类内心的黑暗的产物,古今中外的勇者们都试图打倒它。
经过研究,你发现 Dark 呈现无向图的结构,图中有 N 个节点和两类边,一类边被称为主要边,而另一类被称为附加边。
Dark 有 N–1 条主要边,并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。
另外,Dark 还有 M 条附加边。
你的任务是把 Dark 斩为不连通的两部分。
一开始 Dark 的附加边都处于无敌状态,你只能选择一条主要边切断。
一旦你切断了一条主要边,Dark 就会进入防御模式,主要边会变为无敌的而附加边可以被切断。
但是你的能力只能再切断 Dark 的一条附加边。
现在你想要知道,一共有多少种方案可以击败 Dark。
注意,就算你第一步切断主要边之后就已经把 Dark 斩为两截,你也需要切断一条附加边才算击败了 Dark。
样例
4 1
1 2
2 3
1 4
3 4
3
//看大家都是树上的差分,而一开始是自己想的还没看视频,我的思路差不多当时也觉得先枚举非树边和树边都行,但是我就直接选择了一个先枚举树边的思想
//首先如果是删除一条树边的话,那么就是变成了两个两联通块,这样的话又有附加边使得两个连通块连接,这个时候就要消除这个可能性,如果恰好他们之间只有一条边直接删除即可,如果是多条边这不符合,如果是没有边,那么就是n种
//那么如何考虑呢
//跑两次dfs
//考虑离线的x,y,还有记录编号,然后dfs如果是到了u的时候遍历边,记录出他们的加的边的总和,在记录出一个x,y的最近公共祖先,这个时候如果他们是在你的v(与u相连的点)下方的你就可以回溯的时候加上去,这些就是你这些边在第而个连通块的内部的边,一减就是两个连通块之间的边
//判断为1还是0还是多个
//可惜还少考虑一种情况,调了半天
//上面只有当你x,y其中一个恰好是最近公共祖先才满足
//那么如果不是应该怎么做呢,我是这个时候记录u的个数就不变了res数组,但是sum[y]还是要是要加上去,表示的是y这个链还是又新增加的边,但是对于最后在u合并的时候重复计算了怎么办,额外开一个pos数组记录就好了,
//复杂度可能比较高,跑了2次
//一次总共是3s.一次总共是2.4s
//还有如果是标记编号,vis数组,的话记得是要开M个,因为总共编号是附加边的编号,否则会wa最后两个点//也调了半个小时
//好题好题那么就是只能够删除一条主要边和附加边的可能性,最后如果变成了两部分就是成功的问你有多少个方案
//对于vis的范围
//还需要加上一个树上的总和啊
//多加了很多次啊
//一个总的减去一个标记的那么就是跨边界的
//对于每一个的话就是他们res感觉相互直接会有影响啊
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>
#define x first
#define y second
#define pii pair<ll,ll>
using namespace std;
typedef long long ll;
const int N=1e5+20,M=2e5+30;
ll h[N],e[N*2],ne[N*2],cnt,res[N],f[N][22],dep[N],ans=0,vis[M],sum[N],pos[N];//对于vis的话应该是M的
ll n,m;
vector<pii>s[N];
void add(ll u,ll v)
{
e[cnt]=v,ne[cnt]=h[u],h[u]=cnt++;
}
void dfs(ll u,ll fa,ll d)
{
f[u][0]=fa,dep[u]=d;
for(int i=1;i<=21;i++)
{
f[u][i]=f[f[u][i-1]][i-1];
}
for(int i=h[u];~i;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
dfs(v,u,d+1);
}
}
ll lca(ll x,ll y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=21;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y])
{
x=f[x][i];
}
}
if(x==y) return x;
for(int i=21;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i],y=f[y][i];
}
}
x=f[x][0];
return x;
}
void dfs2(ll u,ll fa)
{
for(int i=h[u];~i;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
dfs2(v,u);
int k=sum[v]-(res[v]+pos[v]);
if(k==1)
{
ans++;
}
else if(!k){
ans+=m;
}
sum[v]-=pos[v];//消除他的影响
res[u]+=res[v];//这个是在记录出出现的记录
sum[u]+=sum[v];
}
for(auto k:s[u])
{
ll v=k.x,id=k.y;
if(!vis[id])
{
res[lca(u,v)]++;
vis[id]=1;
sum[u]++;//加上了新的边
}
else {
ll g=lca(u,v);
if(g!=u)
{
sum[u]++;
pos[g]++;//补偿类
}
}
}
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
ll u,v;
for(int i=1;i<n;i++)
{
cin>>u>>v;
add(u,v);
add(v,u);
}//第一个是建立出一个最小的生成树
dep[0]=0;
dfs(1,0,1);
for(int i=1;i<=m;i++)
{
cin>>u>>v;
s[u].push_back({v,i});
s[v].push_back({u,i});
}
dfs2(1,0);
cout<<ans<<endl;
return 0;
}