题目描述

Description

兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。
兵库县官方也大力发展旅游，为了方便，他们在县内的N个旅游景点上建立了n-1条观光道，构成了一棵图论中的树。同时他们推出了M条观光线路，每条线路由两个节点x和y指定，经过的旅游景点就是树上x到y的唯一路径上的点。保证一条路径只出现一次。
你和你的朋友打算前往兵库县旅游，但旅行社还没有告知你们最终选择的观光线路是哪一条（假设是线路A）。这时候你得到了一个消息：在兵库北有一群丧心病狂的香菜蜜，他们已经选定了一条观光线路（假设是线路B），对这条路线上的所有景点都释放了【精神污染】。这个计划还有可能影响其他的线路，比如有四个景点1-2-3-4，而【精神污染】的路径是1-4，那么1-3,2-4,1-2等路径也被视为被完全污染了。
现在你想知道的是，假设随便选择两条不同的路径A和B，存在一条路径使得如果这条路径被污染，另一条路径也被污染的概率。换句话说，一条路径被另一条路径包含的概率。

Input

第一行两个整数N,M
接下来N-1行，每行两个数a,b，表示A和B之间有一条观光道。
接下来M行，每行两个数x,y，表示一条旅游线路。

Output

所求的概率，以最简分数形式输出。

Sample Input

5 3
1 2
2 3
3 4
2 5
3 5
2 5
1 4

Sample Output

1/3

样例解释
可以选择的路径对有(1,2),(1,3),(2,3)，只有路径1完全覆盖路径2。

HINT

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

题目分析

问题可以转换成:有多少条路径互相包含
那么一条路径的两个端点一定在另一条路径的两个端点的路径之间
那我们可以维护每个点的入栈出栈序 入栈1，出栈-1 ，将所有询问的y塞进x的vector
每到一个点 建立主席树 把x所有的y的入栈位置+1，出栈位置-1
然后枚举所有询问 根据lca进行差分查询
最后答案-m 因为自己包含自己不算

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,tot;
vector<int> s[100010];
vector<int>::iterator it;
int head[100010],to[200010],net[200010];
void add(int x,int y) { net[++tot]=head[x],head[x]=tot,to[tot]=y; }
int deep[100010],top[100010],size[100010],fa[100010],son[100010];
int in[100010],out[100010],cnt;
struct your
{
    int lson,rson,size;
}a[200010*20];
int root[100010],nm;
void update(int &x,int y,int dx,int val,int l,int r)
{
    x=++nm;
    if(l==r) { a[x].size=a[y].size+val; return ; }
    a[x].size=a[y].size+val;
    int mid=(l+r)>>1;
    if(dx<=mid) a[x].rson=a[y].rson,update(a[x].lson,a[y].lson,dx,val,l,mid);
    else a[x].lson=a[y].lson,update(a[x].rson,a[y].rson,dx,val,mid+1,r);
}
int ask(int x,int y,int z,int k,int l,int r,int dx,int dy)
{
    if(dx<=l&&r<=dy) 
        return a[x].size+a[y].size-a[z].size-a[k].size;
    int mid=(l+r)>>1;
    if(dy<=mid) return ask(a[x].lson,a[y].lson,a[z].lson,a[k].lson,l,mid,dx,dy);
    else if(dx>mid) return ask(a[x].rson,a[y].rson,a[z].rson,a[k].rson,mid+1,r,dx,dy);
    else return ask(a[x].lson,a[y].lson,a[z].lson,a[k].lson,l,mid,dx,mid)
               +ask(a[x].rson,a[y].rson,a[z].rson,a[k].rson,mid+1,r,mid+1,dy);   
}
void dfs(int x)
{
    in[x]=++cnt,deep[x]=deep[fa[x]]+1,size[x]=1;
    for(int i=head[x];i;i=net[i])
    {
        if(to[i]==fa[x]) continue;
        fa[to[i]]=x,dfs(to[i]),size[x]+=size[to[i]];
        if(size[son[x]]<size[to[i]]) son[x]=to[i];
    }
    out[x]=++cnt;
}
void dfs2(int x,int temp)
{
    top[x]=temp;
    if(son[x]) dfs2(son[x],temp);
    for(int i=head[x];i;i=net[i])
        if(to[i]!=fa[x]&&to[i]!=son[x]) dfs2(to[i],to[i]);
}
void dfs3(int x)
{
    root[x]=root[fa[x]];
    for(it=s[x].begin();it!=s[x].end();it++)
        update(root[x],root[x],in[*it],1,1,cnt),update(root[x],root[x],out[*it],-1,1,cnt);
    for(int i=head[x];i;i=net[i])
        if(to[i]!=fa[x]) dfs3(to[i]);
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        x=fa[top[x]]; 
    }
    return deep[x]<=deep[y]?x:y;
}
long long ans;
long long gcd(long long x,long long y)
{
    return !y?x:gcd(y,x%y);
}
int main()
{   
    scanf("%d%d",&n,&m);
    for(int x,y,i=1;i<n;i++) 
        scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1),dfs2(1,1);
    for(int x,y,i=1;i<=m;i++) 
        scanf("%d%d",&x,&y),s[x].push_back(y);
    dfs3(1);        
    for(int i=1;i<=n;i++)
        for(it=s[i].begin();it!=s[i].end();it++)
        {
            int l=lca(*it,i);
            ans=ans+ask(root[i],root[*it],root[l],root[fa[l]],1,cnt,in[l],in[i]);
            ans=ans+ask(root[i],root[*it],root[l],root[fa[l]],1,cnt,in[l],in[*it]);
            ans=ans-ask(root[i],root[*it],root[l],root[fa[l]],1,cnt,in[l],in[l]);
            ans--;
        }
    long long tmp=(long long) m*(m-1)/2;
    long long g=gcd(ans,tmp);   
    printf("%lld/%lld",ans/g,tmp/g);
    return 0;   
}