题目描述
输入
输出
样例输入
5 3
1 2
2 3
3 4
2 5
3 5
2 5
1 4
样例输出
1/3
题解
膜拜popoqqq大爷。
由题可知所求为能够覆盖的路径对数/总路径对数。
总对数=m*(m-1)/2，所以只要求能够覆盖的对数即可。
首先我们易知如果某条路径B的两个端点都在另一条路径A上，那么A必然会覆盖B，反之亦然。
那么问题就转化为求A中所有点在多少条B上。
我们设Bi为(xi,yi)，则问题就是求对于所有xi，有多少个yi在A上。
可以先把所有xi对应的所有yi存起来，这里使用vector。
用主席树维护每个xi对应的yi，使用Dfs序，入栈位置+1，出栈位置-1。
那么直接查询[xA,yA]范围内数的个数即可。
当然，每条A不能直接使用Dfs序计算，需要拆成[xA,lca]和[yA,lca]（用倍增lca解决，树剖也可以），再减去重复计算的[lca,lca]。
由于主席树是建立在每个节点的父亲上的，所以每棵树代表着[1,x]，所求路径即为[1,xA]+[1,yA]-[1,lca]-[1,fa[lca]]。
当然自己包含自己是不行的，需要减去。
这样就可以求出能够覆盖的路径对数。
需要说明的是题目中已经声明没有重复路径，所以不需要去重。
最后求gcd再输出即可。
数组大小略坑。
1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 #define N 100010 5 using namespace std; 6 struct data 7 { 8 int x , y , lca; 9 }a[N]; 10 vector<int> v[N]; 11 int fa[N][20] , deep[N] , log[N] , head[N] , to[N * 2] , next[N * 2] , cnt; 12 int lp[N] , rp[N] , pl , q[N] , top; 13 int root[N * 2] , ls[N * 39] , rs[N * 39] , si[N * 39] , tot; 14 bool cmp(data a , data b) 15 { 16 return a.x == b.x ? a.y < b.y : a.x < b.x; 17 } 18 void add(int x , int y) 19 { 20 to[++cnt] = y; 21 next[cnt] = head[x]; 22 head[x] = cnt; 23 } 24 void dfs(int x) 25 { 26 int i; 27 lp[x] = ++pl; 28 q[++top] = x; 29 for(i = head[x] ; i ; i = next[i]) 30 { 31 if(to[i] != fa[x][0]) 32 { 33 fa[to[i]][0] = x; 34 deep[to[i]] = deep[x] + 1; 35 dfs(to[i]); 36 } 37 } 38 rp[x] = ++pl; 39 } 40 int getlca(int x , int y) 41 { 42 int i; 43 if(deep[x] < deep[y]) swap(x , y); 44 for(i = log[deep[x] - deep[y]] ; i >= 0 ; i -- ) 45 if(deep[x] - (1 << i) >= deep[y]) 46 x = fa[x][i]; 47 for(i = log[deep[x]] ; i >= 0 ; i -- ) 48 if(fa[x][i] != fa[y][i]) 49 x = fa[x][i] , y = fa[y][i]; 50 return x == y ? x : fa[x][0]; 51 } 52 void update(int x , int &y , int l , int r , int p , int a) 53 { 54 y = ++tot; 55 if(l == r) 56 { 57 si[y] = si[x] + a; 58 return; 59 } 60 int mid = (l + r) >> 1; 61 if(p <= mid) rs[y] = rs[x] , update(ls[x] , ls[y] , l , mid , p , a); 62 else ls[y] = ls[x] , update(rs[x] , rs[y] , mid + 1 , r , p , a); 63 si[y] = si[ls[y]] + si[rs[y]]; 64 } 65 int query(int w , int x , int y , int z , int l , int r , int b , int e) 66 { 67 if(b <= l && r <= e) 68 return si[w] + si[x] - si[y] - si[z]; 69 int mid = (l + r) >> 1 , sum = 0; 70 if(b <= mid) sum += query(ls[w] , ls[x] , ls[y] , ls[z] , l , mid , b , e); 71 if(e > mid) sum += query(rs[w] , rs[x] , rs[y] , rs[z] , mid + 1 , r , b , e); 72 return sum; 73 } 74 long long gcd(long long a , long long b) 75 { 76 return b ? gcd(b , a % b) : a; 77 } 78 int main() 79 { 80 int n , m , i , j , x , y; 81 long long A = 0 , B = 0 , T; 82 scanf("%d%d" , &n , &m); 83 for(i = 1 ; i < n ; i ++ ) 84 scanf("%d%d" , &x , &y) , add(x , y) , add(y , x); 85 dfs(1); 86 for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1; 87 for(i = 1 ; i <= log[n] ; i ++ ) 88 for(j = 1 ; j <= n ; j ++ ) 89 if(deep[j] >= (1 << i)) 90 fa[j][i] = fa[fa[j][i - 1]][i - 1]; 91 for(i = 1 ; i <= m ; i ++ ) 92 { 93 scanf("%d%d" , &a[i].x , &a[i].y); 94 a[i].lca = getlca(a[i].x , a[i].y); 95 v[a[i].x].push_back(a[i].y); 96 } 97 sort(a + 1 , a + m + 1 , cmp); 98 for(i = 1 ; i <= top ; i ++ ) 99 { 100 x = q[i]; 101 root[x] = root[fa[x][0]]; 102 for(j = 0 ; j < (int)v[x].size() ; j ++ ) 103 { 104 update(root[x] , root[x] , 1 , pl , lp[v[x][j]] , 1); 105 update(root[x] , root[x] , 1 , pl , rp[v[x][j]] , -1); 106 } 107 } 108 for(i = 1 ; i <= m ; i ++ ) 109 { 110 A += query(root[a[i].x] , root[a[i].y] , root[a[i].lca] , root[fa[a[i].lca][0]] , 1 , pl , lp[a[i].lca] , lp[a[i].x]); 111 A += query(root[a[i].x] , root[a[i].y] , root[a[i].lca] , root[fa[a[i].lca][0]] , 1 , pl , lp[a[i].lca] , lp[a[i].y]); 112 A -= query(root[a[i].x] , root[a[i].y] , root[a[i].lca] , root[fa[a[i].lca][0]] , 1 , pl , lp[a[i].lca] , lp[a[i].lca]); 113 A -- ; 114 } 115 B = (long long)m * (m - 1) / 2; 116 T = gcd(A , B); 117 printf("%lld/%lld\n" , A / T , B / T); 118 return 0; 119 }
原文：http://www.cnblogs.com/GXZlegend/p/6296185.html