# bzoj 3772 精神污染

5 3

1 2

2 3

3 4

2 5

3 5

2 5

1 4

1/3

### HINT

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

### 题解

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int in[N], out[N], last, n, m, x, y;
struct data {
int x, y, l, las;
}a[N];
bool comp(data a, data b) {
return in[a.x] == in[b.x] ? in[a.y] < in[a.x] : in[a.x] < in[b.x];
}
struct edge {
int to, next;
}e[N << 1];
int st[N], tot, h[N], f[N][25], ds, cnt[N];
void add(int x, int y) {
e[++tot].next = st[x];
e[tot].to = y, st[x] = tot;
}
void dfs(int x, int pre) {
in[x] = ++ds, h[x] = h[pre] + 1;
for (int i = 1; i < 20; ++i) {
if (h[x] - (1 << i) < 1) break;
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (int i = st[x]; i; i = e[i].next)
if (e[i].to != pre)
f[e[i].to][0] = x, dfs(e[i].to, x);
out[x] = ds;
}
int lca(int x, int y) {
if (x == y) return last = x;
if (h[x] < h[y]) swap(x, y);
for (int i = 19; i >= 0; --i)
while (h[f[x][i]] > h[y])
x = f[x][i];
last = x;
if (h[x] > h[y]) x = f[x][0];
if (x == y) return x;
for (int i = 19; i >= 0; --i)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
int root[N];
struct segt {
int l, r;
long long sum;
}pri[N * 20];
int pot;
void inserts(int pos, int &now, int l, int r) {
pri[++pot] = pri[now], now = pot, pri[now].sum++;
if (l == r) return;
int mid = l + r >> 1;
if (pos <= mid) inserts(pos, pri[now].l, l, mid);
else inserts(pos, pri[now].r, mid + 1, r);
}
long long query(int now, int l, int r, int L, int R) {
if (L <= l && r <= R) return pri[now].sum;
int mid = l + r >> 1; long long ans = 0;
if (L <= mid) ans += query(pri[now].l, l, mid, L, R);
if (R >  mid) ans += query(pri[now].r, mid + 1, r, L, R);
return ans;
}
long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }
long long ans;
main() {
scanf("%d%d", &n, &m);
for (int i = 1; i < n; ++i)
scanf("%d%d", &x, &y),
dfs(1, 0);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
if (in[x] > in[y]) swap(x, y);
a[i].x = x, a[i].y = y, a[i].l = lca(x, y);
a[i].las = last, cnt[a[i].l]++;
}
sort(a + 1, a + m + 1, comp);
for (int i = 1; i <= m; ++i) {
if (i != 1 && in[a[i - 1].x] != in[a[i].x] - 1)
for (int j = in[a[i - 1].x] + 1; j < in[a[i].x]; ++j)
root[j] = root[j - 1];
root[in[a[i].x]] = root[in[a[i - 1].x]];
inserts(in[a[i].y], root[in[a[i].x]], 1, n);
}
for (int i = in[a[m].x] + 1; i <= n; ++i) root[i] = root[i - 1];
for (int i = 1; i <= m; ++i) {
int l = a[i].l; last = a[i].las;
if (l != a[i].x) {
int o = in[a[i].x], u = out[a[i].x], k = in[a[i].y], g = out[a[i].y];
ans += query(root[u], 1, n, k, g) - query(root[o - 1], 1, n, k, g);
} else {
if (a[i].x != a[i].y) {
int o = 1, u = in[last] - 1, k = in[a[i].y], g = out[a[i].y];
if (o <= u) ans += query(root[u], 1, n, k, g) - query(root[o - 1], 1, n, k, g);
o = in[a[i].y], u = out[a[i].y], k = out[last] + 1, g = n;
if (k <= g) ans += query(root[u], 1, n, k, g) - query(root[o - 1], 1, n, k, g);
} else {
int o = 1, u = in[last] - 1, k = in[last], g = out[last];
if (o <= u) ans += query(root[u], 1, n, k, g) - query(root[o - 1], 1, n, k, g);
o = in[last], u = out[last], k = out[last] + 1, g = n;
if (k <= g) ans += query(root[u], 1, n, k, g) - query(root[o - 1], 1, n, k, g);
ans += cnt[last];
}
}
}
ans -= m; long long po = (long long)m * ((long long)m - 1) / 2ll;
long long gc = gcd(ans, po); ans /= gc, po /= gc;
printf("%lld/%lld", ans, po);
}