题意
给一棵有 $n$ 个节点的树，然后再连 $m$ 条不重合的附加边，可以删除一条树边和一条附加边，问有多少种删除方法可以使树断裂。
题解
显然，每次加一条边以后树上一定会形成环，这个环任意断附加边就可以形成树，而树上任意断一条边就可以使树断裂。
但是有可能会形成很多有重叠部分的环，这样按照上述方法不一定可以让树断裂。
所以我们可以对每一条树边 $i$ 记录包含它的环的个数 $f[i]$ ，然后进行分类讨论：
所以我们可以用 $f[i]$ 表示 $i$ 与父节点之间的边被环包含的次数，然后进行分类讨论：
- $f[i]=0$ ，删掉这条边树就断裂了，然后删任意附加边都可以，对答案贡献 $m$ 。
- $f[i]=1$ ，删掉这条边还要删去构成这个环的附加边，对答案贡献 $1$
- $f[i]>1$ ，删掉这条边后无论怎么删都不能使树断裂了，对答案贡献 $0$
统计 $f[i]$ 可以用一个类似差分的方法：对于每次输入的附加边 $(a,b)$ ，我们对 $f[a]++,f[b]++,f[lca(a,b)]-=2$ ，最后跑一遍 $dfs$ 就可以得到 $f[i]$：
$$f[i]+=f[j] , j\in son[i]$$
最后的答案就是所有边的 $f[i]$ 之和。
求 $lca$ 我还是照样用树剖，还冲到了榜第 $5$ ，树剖果然是求 $lca$ 最好的算法。
struct Edge{
int next,to;
} edge[200005];
int n,m,a,b,cnt,ans,head[100005],fa[100005],son[100005],siz[100005],top[100005],deep[100005],f[100005];
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void dfs1(int x,int f,int dep)
{
fa[x]=f;
deep[x]=dep;
siz[x]=1;
int mx=0;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==f) continue;
dfs1(y,x,dep+1);
siz[x]+=siz[y];
//if (siz[x]>mx)
//{
// mx=siz[x];
// son[x]=y;
//}
//update 2020.11.5
if (siz[y]>mx)
{
mx=siz[y];
son[x]=y;
}
}
}
void dfs2(int x,int topf)
{
top[x]=topf;
if (!son[x]) return;
dfs2(son[x],topf);
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==fa[x] || y==son[x]) continue;
dfs2(y,y);
}
}
inline int get_lca(int u,int v)
{
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);
u=fa[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);
return u;
}
void dfs3(int x)
{
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==fa[x]) continue;
dfs3(y);
f[x]+=f[y];
}
}
int main()
{
n=read(); m=read();
for (int i=1;i<n;i++)
{
a=read(); b=read();
add(a,b);
add(b,a);
}
dfs1(1,0,1);
dfs2(1,1);
for (int i=1;i<=m;i++)
{
a=read(); b=read();
f[a]++; f[b]++; f[get_lca(a,b)]-=2;
}
dfs3(1);
for (int i=2;i<=n;i++) ans+=!f[i] ? m : f[i]==1 ? 1 : 0;
printf("%d",ans);
return 0;
}