题目描述
兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。
兵库县官方也大力发展旅游，为了方便，他们在县内的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，表示一条旅游线路。
输出
所求的概率，以最简分数形式输出。
样例输入
5 3
1 2
2 3
3 4
2 5
3 5
2 5
1 4
样例输出
1/3
题解
Orz 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再输出即可。
数组大小略坑。
#include <cstdio>
#include <vector>
#include <algorithm>
#define N 100010
using namespace std;
struct data
{
int x , y , lca;
}a[N];
vector<int> v[N];
int fa[N][20] , deep[N] , log[N] , head[N] , to[N * 2] , next[N * 2] , cnt;
int lp[N] , rp[N] , pl , q[N] , top;
int root[N * 2] , ls[N * 39] , rs[N * 39] , si[N * 39] , tot;
bool cmp(data a , data b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
void add(int x , int y)
{
to[++cnt] = y;
next[cnt] = head[x];
head[x] = cnt;
}
void dfs(int x)
{
int i;
lp[x] = ++pl;
q[++top] = x;
for(i = head[x] ; i ; i = next[i])
{
if(to[i] != fa[x][0])
{
fa[to[i]][0] = x;
deep[to[i]] = deep[x] + 1;
dfs(to[i]);
}
}
rp[x] = ++pl;
}
int getlca(int x , int y)
{
int i;
if(deep[x] < deep[y]) swap(x , y);
for(i = log[deep[x] - deep[y]] ; i >= 0 ; i -- )
if(deep[x] - (1 << i) >= deep[y])
x = fa[x][i];
for(i = log[deep[x]] ; i >= 0 ; i -- )
if(fa[x][i] != fa[y][i])
x = fa[x][i] , y = fa[y][i];
return x == y ? x : fa[x][0];
}
void update(int x , int &y , int l , int r , int p , int a)
{
y = ++tot;
if(l == r)
{
si[y] = si[x] + a;
return;
}
int mid = (l + r) >> 1;
if(p <= mid) rs[y] = rs[x] , update(ls[x] , ls[y] , l , mid , p , a);
else ls[y] = ls[x] , update(rs[x] , rs[y] , mid + 1 , r , p , a);
si[y] = si[ls[y]] + si[rs[y]];
}
int query(int w , int x , int y , int z , int l , int r , int b , int e)
{
if(b <= l && r <= e)
return si[w] + si[x] - si[y] - si[z];
int mid = (l + r) >> 1 , sum = 0;
if(b <= mid) sum += query(ls[w] , ls[x] , ls[y] , ls[z] , l , mid , b , e);
if(e > mid) sum += query(rs[w] , rs[x] , rs[y] , rs[z] , mid + 1 , r , b , e);
return sum;
}
long long gcd(long long a , long long b)
{
return b ? gcd(b , a % b) : a;
}
int main()
{
int n , m , i , j , x , y;
long long A = 0 , B = 0 , T;
scanf("%d%d" , &n , &m);
for(i = 1 ; i < n ; i ++ )
scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);
dfs(1);
for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1;
for(i = 1 ; i <= log[n] ; i ++ )
for(j = 1 ; j <= n ; j ++ )
if(deep[j] >= (1 << i))
fa[j][i] = fa[fa[j][i - 1]][i - 1];
for(i = 1 ; i <= m ; i ++ )
{
scanf("%d%d" , &a[i].x , &a[i].y);
a[i].lca = getlca(a[i].x , a[i].y);
v[a[i].x].push_back(a[i].y);
}
sort(a + 1 , a + m + 1 , cmp);
for(i = 1 ; i <= top ; i ++ )
{
x = q[i];
root[x] = root[fa[x][0]];
for(j = 0 ; j < (int)v[x].size() ; j ++ )
{
update(root[x] , root[x] , 1 , pl , lp[v[x][j]] , 1);
update(root[x] , root[x] , 1 , pl , rp[v[x][j]] , -1);
}
}
for(i = 1 ; i <= m ; i ++ )
{
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]);
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]);
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]);
A -- ;
}
B = (long long)m * (m - 1) / 2;
T = gcd(A , B);
printf("%lld/%lld
" , A / T , B / T);
return 0;
}