- 1#include 2#include 3#include 4#include 5#include 6#define LL long long 7#define ls x * 2,
- l,
- mid 8#define rs x * 2 + 1,
- mid + 1,
- r 9#define N 200005 10 using namespace std;
- 11 LL gcd(LL a, LL b) 12 {
- 13
- if (!b) return a;
- 14
- return gcd(b, a % b);
- 15
- }
- 16 int n,
- m;
- 17 int head[N],
- ver[N * 2],
- nxt[N * 2],
- tot;
- 18 void add(int a, int b) 19 {
- 20 tot++;
- nxt[tot] = head[a];
- head[a] = tot;
- ver[tot] = b;
- return;
- 21
- }
- 22 int dep[N],
- fa[N][20],
- dfn[N],
- z,
- ed[N];
- 23 void dfs(int x, int f) 24 {
- 25 dfn[x] = ++z;
- 26
- for (int i = head[x]; i; i = nxt[i]) 27 {
- 28
- if (ver[i] == f) continue;
- 29 dep[ver[i]] = dep[x] + 1;
- 30 fa[ver[i]][0] = x;
- 31 dfs(ver[i], x);
- 32
- }
- ed[x] = z;
- 33
- }
- 34 void yu() 35 {
- 36
- for (int i = 1; i <= 17; i++) 37 {
- 38
- for (int j = 1; j <= n; j++) 39 {
- 40 fa[j][i] = fa[fa[j][i - 1]][i - 1];
- 41
- }
- 42
- }
- return;
- 43
- }
- 44 int lca(int x, int y) 45 {
- 46
- if (dep[x] < dep[y]) swap(x, y);
- 47
- for (int i = 17; i >= 0; i--) 48 {
- 49
- if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
- 50
- }
- 51
- if (x == y) return x;
- 52
- for (int i = 17; i >= 0; i--) 53 {
- 54
- if (fa[x][i] != fa[y][i]) 55 {
- 56 x = fa[x][i];
- y = fa[y][i];
- 57
- }
- 58
- }
- 59
- return fa[x][0];
- 60
- }
- 61 int a[N * 8];
- 62 void add(int x, int l, int r, int pos, int z) 63 {
- 64
- if (l == r) 65 {
- 66 a[x] += z;
- 67
- return;
- 68
- }
- 69 int mid = (l + r) >> 1;
- 70
- if (pos <= mid) add(ls, pos, z);
- 71
- else add(rs, pos, z);
- 72 a[x] = a[x * 2] + a[x * 2 + 1];
- 73
- }
- 74 int qur(int x, int l, int r, int ll, int rr) 75 {
- 76
- if (ll > rr) return 0;
- 77
- if (ll <= l && rr >= r) 78 {
- 79
- return a[x];
- 80
- }
- 81 int mid = (l + r) >> 1;
- 82
- if (ll > mid) return qur(rs, ll, rr);
- 83
- if (rr <= mid) return qur(ls, ll, rr);
- 84
- return qur(rs, ll, rr) + qur(ls, ll, rr);
- 85
- }
- 86 struct qr 87 {
- 88 int x,
- y;
- 89
- }
- q[N];
- 90 struct node 91 {
- 92 int op,
- y;
- 93 node(int xx, int yy) 94 {
- 95 op = xx;
- y = yy;
- 96
- }
- 97
- };
- 98 int faa(int x, int y) 99 {
- 100
- for (int i = 17; i >= 0; i--) 101 {
- 102
- if (dep[fa[x][i]] > dep[y]) x = fa[x][i];
- 103
- }
- 104
- return x;
- 105
- }
- 106 vectorlazy[N];
- 107 LL ans;
- 108 int sb[N];
- 109 void dp(int x, int f) 110 {
- 111
- for (int i = 0; i) 112 {
- 113
- if (!lazy[x][i].op) continue;
- 114
- if (lazy[x][i].op == 1) 115 {
- 116 ans -= qur(1, 1, n, dfn[lazy[x][i].y], ed[lazy[x][i].y]);
- 117
- }
- 118
- else 119 {
- 120 int yy = lazy[x][i].y;
- 121 int now = faa(x, yy);
- 122 ans -= qur(1, 1, n, 1, dfn[now] - 1) + qur(1, 1, n, ed[now] + 1, n);
- 123
- if (x == yy) 124 {
- 125 ans -= qur(1, 1, n, dfn[x], dfn[x]);
- 126
- }
- 127
- }
- 128
- }
- 129
- for (int i = 0; i) 130 {
- 131 add(1, 1, n, dfn[lazy[x][i].y], 1);
- 132
- if (lazy[x][i].op == 1) 133 {
- 134 int uu = lca(x, lazy[x][i].y);
- 135 sb[uu]++;
- 136
- }
- 137
- }
- 138
- for (int i = head[x]; i; i = nxt[i]) 139 {
- 140
- if (ver[i] == f) continue;
- 141 dp(ver[i], x);
- 142
- }
- 143
- for (int i = 0; i) 144 {
- 145
- if (!lazy[x][i].op) continue;
- 146
- if (lazy[x][i].op == 1) 147 {
- 148 ans += qur(1, 1, n, dfn[lazy[x][i].y], ed[lazy[x][i].y]);
- 149
- }
- 150
- else 151 {
- 152 int yy = lazy[x][i].y;
- 153 int now = faa(x, yy);
- 154
- if (x == yy) 155 {
- 156 ans += qur(1, 1, n, dfn[x], dfn[x]);
- 157 ans += sb[x];
- 158
- }
- 159 ans += qur(1, 1, n, 1, dfn[now] - 1) + qur(1, 1, n, ed[now] + 1, n);
- 160
- }
- 161
- }
- 162
- }
- 163 int main() 164 {
- 165 scanf("%d%d", &n, &m);
- 166 int t1,
- t2;
- 167
- for (int i = 1; i) 168 {
- 169 scanf("%d%d", &t1, &t2);
- 170 add(t1, t2);
- add(t2, t1);
- 171
- }
- 172 ans = -m;
- 173 dep[1] = 1;
- 174 dfs(1, -1);
- 175 yu();
- 176
- for (int i = 1; i <= m; i++) 177 {
- 178 scanf("%d%d", &q[i].x, &q[i].y);
- 179 int tmp = lca(q[i].x, q[i].y);
- 180
- if (tmp == q[i].x) 181 {
- 182 lazy[q[i].y].push_back(node(2, q[i].x));
- 183
- if (q[i].x != q[i].y) lazy[q[i].x].push_back(node(0, q[i].y));
- 184
- }
- 185
- else if (tmp == q[i].y) 186 {
- 187 lazy[q[i].y].push_back(node(0, q[i].x));
- 188 lazy[q[i].x].push_back(node(2, q[i].y));
- 189
- }
- 190
- else 191 {
- 192 lazy[q[i].x].push_back(node(1, q[i].y));
- 193 lazy[q[i].y].push_back(node(0, q[i].x));
- 194
- }
- 195
- }
- 196 dp(1, -1);
- 197 LL tt = (LL) m * (m - 1) / 2;
- 198 LL oo = gcd(tt, ans);
- 199 printf("%lld/%lld\n", ans / oo, tt / oo);
- 200
- return 0;
- 201
- }
来源: http://www.bubuko.com/infodetail-1948477.html