兵库县位于日本列岛的*位置，北临日本海，南面濑户内海直通太平洋，*部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。

兵库县官方也大力发展旅游，为了方便，他们在县内的N个旅游景点上建立了n-1条观光道，构成了一棵图论中的树。同时他们推出了M条观光线路，每条线路由两个节点x和y指定，经过的旅游景点就是树上x到y的唯一路径上的点。保证一条路径只出现一次。

你和你的朋友打算前往兵库县旅游，但旅行社还没有告知你们最终选择的观光线路是哪一条（假设是线路A）。这时候你得到了一个消息：在兵库北有一群丧心病狂的香菜蜜，他们已经选定了一条观光线路（假设是线路B），对这条路线上的所有景点都释放了【精神污染】。这个计划还有可能影响其他的线路，比如有四个景点1-2-3-4，而【精神污染】的路径是1-4，那么1-3,2-4,1-2等路径也被视为被完全污染了。

现在你想知道的是，假设随便选择两条不同的路径A和B，存在一条路径使得如果这条路径被污染，另一条路径也被污染的概率。换句话说，一条路径被另一条路径包含的概率。

 

第一行两个整数N,M

接下来N-1行，每行两个数a,b，表示A和B之间有一条观光道。

接下来M行，每行两个数x,y，表示一条旅游线路。

 

100%的数据满足：N,M<=100000

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<set>

 #include<vector>

 #include<algorithm>

 #include<cmath>

 #define ll long long

 #define N 100007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch>''||ch<''){if (ch=='-') f=-;ch=getchar();}

     while(ch<=''&&ch>=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,ind,sz;

 ll fz,fm;

 int ls[N*],rs[N*],sum[N*];

 int deep[N],root[N*],in[N],out[N];

 int fa[N][],ci[];

 vector<int>a[N];

 int cnt,hed[N],nxt[N*],rea[N*];

 struct query

 {

     int x,y;

 }q[N];

 bool operator<(query a,query b)

 {

     if(a.x==b.x)return a.y<b.y;

     else return a.x<b.x;

 }

 ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}

 void add(int u,int v)

 {

     nxt[++cnt]=hed[u];

     hed[u]=cnt;

     rea[cnt]=v;

 }

 void dfs(int x)

 {

     for(int i=;(<<i)<=deep[x];i++)

         fa[x][i]=fa[fa[x][i-]][i-];

     in[x]=++ind;

     for(int i=hed[x];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if(v!=fa[x][])

         {

             fa[v][]=x;

             deep[v]=deep[x]+;

             dfs(v);

         }

     }

     out[x]=++ind;

 }

 inline void update(int p){sum[p]=sum[ls[p]]+sum[rs[p]];}

 /*void ins(int yl,int &xz,int l,int r,int pos,int val)

 {

     xz=++sz,ls[xz]=ls[yl],rs[xz]=rs[yl];

     if(l==r)

     {

         sum[xz]=sum[yl]+val;

         return;

     }

     int mid=(l+r)>>1;

     if(pos<=mid) ins(ls[yl],ls[xz],l,mid,pos,val);

     else ins(rs[yl],rs[xz],mid+1,r,pos,val);

     update(xz);

 }*/

 int insert(int x,int l,int r,int pos,int val)

 {

     int t=++sz;

     ls[t]=ls[x];rs[t]=rs[x];

     if(l==r){sum[t]=sum[x]+val;return t;}

     int mid=(l+r)>>;

     if(pos<=mid)ls[t]=insert(ls[t],l,mid,pos,val);

     else rs[t]=insert(rs[t],mid+,r,pos,val);

     sum[t]=sum[ls[t]]+sum[rs[t]];

     return t;

 }

 int query(int p1,int p2,int p3,int p4,int l,int r,int st,int ed)

 {

     int mid=(l+r)>>;

     if(l==st&&r==ed) {return sum[p1]+sum[p2]-sum[p3]-sum[p4];}

     if(ed<=mid) return query(ls[p1],ls[p2],ls[p3],ls[p4],l,mid,st,ed);

     else if(st>mid) return query(rs[p1],rs[p2],rs[p3],rs[p4],mid+,r,st,ed);

     else return query(ls[p1],ls[p2],ls[p3],ls[p4],l,mid,st,mid)+query(rs[p1],rs[p2],rs[p3],rs[p4],mid+,r,mid+,ed);

 }

 /*

 void build(int x)

 {

     root[0]=root[fa[x][0]];

     for(int i=0;i<a[x].size();i++)

     {

         ins(root[0],root[N-1],1,ind,in[a[x][i]],1);

         ins(root[N-1],root[x],1,ind,out[a[x][i]],-1);

     }

     for(int i=hed[x];i!=-1;i=nxt[i])

     {

         int v=rea[i];

         if(v!=fa[x][0]) build(v);

     }

 }*/

 void build(int x)

 {

     root[x]=root[fa[x][]];

     for(int i=;i<a[x].size();i++)

     {

         root[x]=insert(root[x],,ind,in[a[x][i]],);

         root[x]=insert(root[x],,ind,out[a[x][i]],-);

     }

     for(int i=hed[x];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if(v!=fa[x][])

             build(v);

     }

 }

 int lca(int a,int b)

 {

     if (deep[a]<deep[b]) swap(a,b);

     int i;for (i=;(<<i)<=deep[a];i++);i--;

     for (int j=i;j>=;j--)

         if (deep[a]-(<<j)>=deep[b]) a=fa[a][j];

     if (a==b) return a;

     for (int j=i;j>=;j--)

         if (fa[a][j]!=fa[b][j]) a=fa[a][j],b=fa[b][j];

     return fa[a][];

 }

 void solve()

 {

     for(int i=;i<=m;i++)

     {

         int x=q[i].x,y=q[i].y,f=lca(x,y);

         fz+=query(root[x],root[y],root[f],root[fa[f][]],,ind,in[f],in[x]);

         fz+=query(root[x],root[y],root[f],root[fa[f][]],,ind,in[f],in[y]);

         fz-=query(root[x],root[y],root[f],root[fa[f][]],,ind,in[f],in[f]);

         fz--;

     }

 }

 inline void init()

 {

     ci[]=;

     for(int i=;i<;i++)ci[i]=ci[i-]<<;

     memset(hed,-,sizeof(hed));

     n=read();m=read();

     for(int i=;i<n;i++)

     {

         int u=read(),v=read();

         add(u,v),add(v,u);//加边，没什么问题。

     }

     for(int i=;i<=m;i++)

     {

         int x=read(),y=read();

         a[x].push_back(y);//在边的起点放入另外一个端点。

         q[i].x=x,q[i].y=y;

     }

     sort(q+,q+m+);//q按照x为第一关键字来排序。

 }

 int main()

 {

     freopen("fzy.in","r",stdin);

     freopen("fzy.out","w",stdout);

     init(),dfs(),build(),solve();

     fm=(ll)m*(m-)/;

     ll t=gcd(fz,fm);

     fz/=t;fm/=t;

     printf("%lld/%lld",fz,fm);

 }