1 /**************************************************************  2     Problem: 3772  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:3960 ms  7     Memory:62540 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12 #include <vector> 13   14 using namespace std; 15 typedef long long ll; 16 const int N = 100010; 17 const int M = N; 18 const int cnt_segment = 3804000; 19   20 struct edge { 21   int next, to; 22   edge() {} 23   edge(int _n, int _t) : next(_n), to(_t) {}  24 } e[N << 1]; 25   26 struct Query { 27   int x, y; 28   Query() {} 29   Query(int _x, int _y) : x(_x), y(_y) {} 30   31   inline bool operator < (const Query &a) const { 32     return x == a.x ? y < a.y : x < a.x; 33   } 34   inline bool operator == (const Query &a) const { 35     return x == a.x && y == a.y; 36   } 37 } Q[M]; 38   39 struct seg_node { 40   seg_node *ls, *rs; 41   int val; 42 } *seg[N], mempool[cnt_segment], *cnt_seg = mempool; 43   44 struct tree_node { 45   int fa[18], dep, st, ed; 46 } tr[N]; 47   48 int n, m; 49 int first[N], tot; 50 int cnt_dfs; 51 ll ans1, ans2, g; 52 vector <int> a[N]; 53   54 inline int read() { 55   int x = 0; 56   char ch = getchar(); 57   while (ch < ‘0‘ || ‘9‘ < ch) 58     ch = getchar(); 59   while (‘0‘ <= ch && ch <= ‘9‘) 60     (x *= 10) += ch - ‘0‘, ch = getchar(); 61   return x; 62 } 63   64 inline ll gcd(ll a, ll b) { 65   return a ? gcd(b % a, a) : b; 66 } 67   68 inline void Add_edges(int x, int y) { 69   e[++tot] = edge(first[x], y), first[x] = tot; 70   e[++tot] = edge(first[y], x), first[y] = tot; 71 } 72   73 #define mid (l + r >> 1) 74 void seg_modify(seg_node *&p, int l, int r, int pos, int v) { 75   *(++cnt_seg) = *p, p = cnt_seg, p -> val += v; 76   if (l == r) return; 77   if (pos <= mid) seg_modify(p -> ls, l, mid, pos, v); 78   else seg_modify(p -> rs, mid + 1, r, pos, v); 79 } 80   81 int get_ans(seg_node *p1, seg_node *p2, seg_node *p3, seg_node *p4, int l, int r, int x, int y) { 82   if (l == x && y == r) 83     return p1 -> val + p2 -> val - p3 -> val - p4 -> val; 84   if (y <= mid) 85     return get_ans(p1 -> ls, p2 -> ls, p3 -> ls, p4 -> ls, l, mid, x, y); 86   if (mid < x) 87     return get_ans(p1 -> rs, p2 -> rs, p3 -> rs, p4 -> rs, mid + 1, r, x, y); 88   return get_ans(p1 -> ls, p2 -> ls, p3 -> ls, p4 -> ls, l, mid, x, mid) + 89     get_ans(p1 -> rs, p2 -> rs, p3 -> rs, p4 -> rs, mid + 1, r, mid + 1, y); 90 } 91 #undef mid 92   93 #define y e[x].to 94 void dfs1(int p) { 95   int x; 96   tr[p].st = ++cnt_dfs; 97   for (x = 1; x <= 17; ++x) 98     tr[p].fa[x] = tr[tr[p].fa[x - 1]].fa[x - 1]; 99   for (x = first[p]; x; x = e[x].next)100     if (y != tr[p].fa[0]) {101       tr[y].fa[0] = p, tr[y].dep = tr[p].dep + 1;102       dfs1(y);103     }104   tr[p].ed = ++cnt_dfs;105 }106  107 void dfs2(int p) {108   int x;109   vector <int> :: iterator IT;110   seg[p] = seg[tr[p].fa[0]];111   for (IT = a[p].begin(); IT != a[p].end(); ++IT) {112     seg_modify(seg[p], 1, n << 1, tr[*IT].st, 1);113     seg_modify(seg[p], 1, n << 1, tr[*IT].ed, -1);114   }115   for (x = first[p]; x; x = e[x].next)116     if (y != tr[p].fa[0]) dfs2(y);117 }118 #undef y119  120 inline int get_lca(int x, int y) {121   int i;122   if (tr[x].dep < tr[y].dep) swap(x, y);123   for (i = 17; ~i; --i)124     if (tr[tr[x].fa[i]].dep >= tr[y].dep)125       x = tr[x].fa[i];126   for (i = 17; ~i; --i)127     if (tr[x].fa[i] != tr[y].fa[i])128       x = tr[x].fa[i], y = tr[y].fa[i];129   return x == y ? x : tr[x].fa[0];130 }131  132 int main() {133   int i, j, x, y, lca;134   n = read(), m = read();135   for (i = 1; i < n; ++i) Add_edges(read(), read());136   for (i = 1; i <= m; ++i) {137     x = read(), y = read();138     a[x].push_back(y);139     Q[i] = Query(x, y);140   }141   seg[0] = ++cnt_seg, seg[0] -> ls = seg[0] -> rs = seg[0];142   tr[1].dep = 1;143   dfs1(1);144   dfs2(1);145   for (i = 1; i <= m; ++i) {146     x = Q[i].x, y = Q[i].y, lca = get_lca(x, y);147     ans1 += get_ans(seg[x], seg[y], seg[lca], seg[tr[lca].fa[0]], 1, n << 1, tr[lca].st, tr[x].st);148     ans1 += get_ans(seg[x], seg[y], seg[lca], seg[tr[lca].fa[0]], 1, n << 1, tr[lca].st, tr[y].st);149     ans1 -= get_ans(seg[x], seg[y], seg[lca], seg[tr[lca].fa[0]], 1, n << 1, tr[lca].st, tr[lca].st);150     --ans1;151   }152   sort(Q + 1, Q + m + 1);153   for (i = 1; i <= m; i = j) {154     for (j = i + 1; j <= m && Q[i] == Q[j]; ++j);155     ans1 -= (ll) (j - i) * (j - i - 1) >> 1;156     }157   ans2 = (ll) m * (m - 1) >> 1;158   g = gcd(ans1, ans2);159   printf("%lld/%lld\n", ans1 / g, ans2 / g);160   return 0;161 }