参见http://blog.csdn.net/popoqqq/article/details/43122821
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+;
ll ans;int n,m,idx,cnt,head[N],tmp,rt[N],f[N][],d[N],in[N],out[N];
vector<int>p[N];
struct tree
{
int w,l,r;
}t[];
struct node
{
int x,y;
}q[N];
bool cmp(node a,node b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
struct edge
{
int to,nex;
}e[N<<];
void add(int x,int y)
{
e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;
}
void change(int &x,int y,int l,int r,int p,int w)
{
if(x==y||!x)x=++tmp,t[x]=t[y];
if(l==r){
t[x].w+=w;return;
}
int mid=l+r>>;
if(p<=mid)change(t[x].l,t[y].l,l,mid,p,w);
else change(t[x].r,t[y].r,mid+,r,p,w);
t[x].w=t[t[x].l].w+t[t[x].r].w;
}
void dfs(int x)
{
in[x]=++idx;
for(int i=;i<;++i)f[x][i]=f[f[x][i-]][i-];
for(int i=head[x];i;i=e[i].nex)
{
int y=e[i].to;
if(y==f[x][])continue;
d[y]=d[x]+;f[y][]=x;
dfs(y);
}
out[x]=++idx;
return;
}
void dfs2(int x)
{
for(int i=;i<p[x].size();++i)
{
change(rt[x],rt[f[x][]],,*n,in[p[x][i]],);
change(rt[x],rt[f[x][]],,*n,out[p[x][i]],-);
}
if(!p[x].size())rt[x]=rt[f[x][]];
for(int i=head[x];i;i=e[i].nex)
{
int y=e[i].to;
if(y==f[x][])continue;
dfs2(y);
}
}
int query(int rt1,int rt2,int rt3,int rt4,int l,int r,int L,int R)
{
if(l==L&&r==R)return t[rt1].w+t[rt2].w-t[rt3].w-t[rt4].w;//线段树动态开点
int mid=l+r>>;
if(R<=mid)return query(t[rt1].l,t[rt2].l,t[rt3].l,t[rt4].l,l,mid,L,R);
else if(L>mid)return query(t[rt1].r,t[rt2].r,t[rt3].r,t[rt4].r,mid+,r,L,R);
else return query(t[rt1].l,t[rt2].l,t[rt3].l,t[rt4].l,l,mid,L,mid)+query(t[rt1].r,t[rt2].r,t[rt3].r,t[rt4].r,mid+,r,mid+,R);
}
int lca(int x,int y)
{
if(d[x]<d[y])swap(x,y);
int tt=d[x]-d[y];
for(int i=;i<;++i)
if(tt&(<<i))x=f[x][i];
for(int i=;i>=;--i)
if(f[x][i]!=f[y][i])
{
x=f[x][i];y=f[y][i];
}
return x==y?x:f[x][];
}
ll gcd(ll a,ll b)
{
return b==?a:gcd(b,a%b);
}
int main()
{
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=;i<n;++i)
{
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
for(int i=;i<=m;++i)
{
scanf("%d%d",&q[i].x,&q[i].y);
if(q[i].x>q[i].y)swap(q[i].x,q[i].y);
p[q[i].x].push_back(q[i].y);
}
dfs();dfs2();
for(int i=;i<=m;++i)
{
x=q[i].x,y=q[i].y,z=lca(x,y);
ans+=query(rt[x],rt[y],rt[z],rt[f[z][]],,*n,in[z],in[x]);
ans+=query(rt[x],rt[y],rt[z],rt[f[z][]],,*n,in[z],in[y]);
ans-=query(rt[x],rt[y],rt[z],rt[f[z][]],,*n,in[z],in[z]);
ans--;
}
sort(q+,q++m,cmp);
for(int i=,j=i+;i<=m;i=j,j=i+)
{
while(j<=m&&q[i].x==q[j].x&&q[i].y==q[j].y)++j;
ans-=1ll*(j-i)*(j-i-)/;
}
ll b=1ll*m*(m-)/,Gcd=gcd(ans,b);
printf("%lld/%lld\n",ans/Gcd,b/Gcd);
return ;
}