Description
无向图中有N个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark有N – 1条主要边，并且Dark的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark还有M条附加边。
你的任务是把Dark斩为不连通的两部分。一开始Dark的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断Dark的一条附加边。现在你想要知道，一共有多少种方案可以击败Dark。注意，就算你第一步切断主要边之后就已经把Dark斩为两截，你也需要切断一条附加边才算击败了Dark。
Input
第一行包含两个整数N和M。
之后N – 1行，每行包括两个整数A和B，表示A和B之间有一条主要边。
之后M行以同样的格式给出附加边。
Output
输出一个整数表示答案。
Sample Input
4 1
1 2
2 3
1 4
3 4
Sample Output
3
Hint
对于20% 的数据，N≤100，M≤100。
对于100% 的数据，N≤100 000，M≤200 000。数据保证答案不超过2^31– 1。
Solution
对于一条附加边，可以对两点到它们的LCA之间的边产生影响
当一条主要边不受影响时，可以和任意一条附加边产生组合。
当一条主要边只受一条附加边影响时，可以与这一条附加边产生组合
当一条主要边受多条附加边影响时，删了这条主要边，仍有两条以上的边连接两边，够不成独立区域
故进行树上差分即可 （dfs序）
Code
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define rep(i,a,b) for(RG i=a;i<=b;i++)
#define per(i,a,b) for(RG i=a;i>=b;i--)
#define inf (1<<30)
#define maxn 100005
#define maxm 200005
using namespace std;
int n,m,cnt,id,ans;
int head[maxn],cf[maxn];
int son[maxn],sz[maxn],fa[maxn],dep[maxn],dfn[maxn],top[maxn];
struct E{
int v,next;
}e[maxn<<]; inline int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} inline void add(int u,int v)
{
e[++cnt].v=v,e[cnt].next=head[u],head[u]=cnt;
} void dfs1(int u,int pa)
{
sz[u]=,son[u]=,fa[u]=pa,dep[u]=dep[pa]+;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==pa) continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
} void dfs2(int u,int tp)
{
dfn[u]=++id,top[u]=tp;
if(!son[u]) return;
dfs2(son[u],tp);
for(int i=head[u];i;i=e[i].next)
if(e[i].v!=son[u]&&e[i].v!=fa[u]) dfs2(e[i].v,e[i].v); } int work(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
--cf[dfn[x]+],++cf[dfn[top[x]]];
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
++cf[dfn[x]+],--cf[dfn[y]+];
} int main()
{
n=read(),m=read();
RG u,v;
rep(i,,n) u=read(),v=read(),add(u,v),add(v,u);
dfs1(,);
dfs2(,);
rep(i,,m)
{
u=read(),v=read();
work(u,v);
}
rep(i,,n)
{
cf[i]+=cf[i-];
if(!cf[i]) ans+=m;
else if(cf[i]==) ans++;
}
printf("%d\n",ans);
return ;
}