Description：

给一棵大小为 $n$ 的树和树上的 $m$ 条路径，问一条路径被另一条包含的概率。

$1\le n \le 100000$

Solution：

首先概率可以转化为可行方案数除以总方案数。对每条路经 $(x,y)$ ，对 $x$ 开一个 $vector$ 把 $y$ 存进去，由于一条路径被另一条包含当且仅当这条路径两个端点都在另一条路径上，我们可以换一个角度，从出入栈序列的角度思考这个问题，对于两条路径 $(x,y)$ 和 $(x,z)$ ，如果后者包含前者，那么有几种情况，一是 $y$ 在 $(x,lca(x,z))$ 上，这样 $y$ 的入栈序一定在 $x$ 和 $lca(x,z)$ 的入栈序之间，出栈序在 $x$ 的入栈序之后，另一种是 $y$ 在 $(lca(x,z),z)$ 上，那么 $y$ 的入栈序在 $lca(x,z)$ 和 $z$ 的入栈序之间，出栈序在 $z$ 的入栈序之后，也就是说我们只要查询入栈序在 $[in[x],in[lca(x,z)]]$ 和 $[in[lca(x,z)],in[z]]$ 之间的所有点就得到了所有从 $x$ 出发，终点在 $(x,z)$ 的路径上的路径，注意 $lca$ 计算了两次要减掉一次，可以维护出入栈序列，入栈为 $1$ ，出栈为 $-1$ ，用线段树维护 $sum$ 即可。但是这样计算的是所有从 $x$ 出发的路径，而出发节点可以在路径 $(x,z)$ 上，在树上建主席树就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

pair<int,int> r[MAXN];

#define fi first

#define se second

struct edge

{

    int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

    return;

}

vector<int> g[MAXN];

int fa[MAXN],dep[MAXN],siz[MAXN],son[MAXN],top[MAXN];

void dfs1(int k,int depth)

{

    dep[k] = depth;siz[k] = 1;

    for(register int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa[k])

        {

            fa[e[i].to] = k;

            dfs1(e[i].to,depth + 1);

            siz[k] += siz[e[i].to];

            if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

            {

                son[k] = e[i].to;    

            }

        }

    }

    return;

}

void dfs2(int k,int tp)

{

    top[k] = tp;

    if(son[k] == 0)return;

    dfs2(son[k],tp);

    for(register int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa[k] && e[i].to != son[k])

        {

            dfs2(e[i].to,e[i].to);

        }

    }

    return;

}

inline int LCA(int a,int b)

{

    while(top[a] != top[b])

    {

        if(dep[top[a]] < dep[top[b]])swap(a,b);

        a = fa[a];    

    }

    return (dep[a] < dep[b] ? a : b);

}

int in[MAXN],out[MAXN],th[MAXN << 1],tot = 0;

typedef long long ll;

struct node

{

    int lc,rc;

    ll sum;

    node(){sum = 0;}

}t[MAXN * 40];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root[MAXN];

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

    rt = newnode();

    if(l == r)return;

    build(t[rt].lc,l,mid);

    build(t[rt].rc,mid + 1,r);

    return;

}

void add(int &rt,int p,int k,int l,int r)

{

    register int s = newnode();t[s] = t[rt];rt = s;

    if(l == r)

    {

        t[rt].sum += k;

        return;    

    }

    if(p <= mid)add(t[rt].lc,p,k,l,mid);

    else add(t[rt].rc,p,k,mid + 1,r);

    t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

    return;

}

void efs1(int k,int fa)

{

    in[k] = ++tot;th[tot] = k;

    for(register int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa)

        {

            efs1(e[i].to,k);

        }    

    }

    out[k] = ++tot;th[tot] = -k;

    return;

}

void efs2(int k,int fa)

{

    root[k] = root[fa];

    for(register vector<int>::iterator i = g[k].begin();i != g[k].end();++i)

    {

        add(root[k],in[*i],1,1,2 * n);

        add(root[k],out[*i],-1,1,2 * n);

    }

    for(register int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa)

        {

            efs2(e[i].to,k);

        }

    }

    return;

}

ll query(int a,int b,int c,int d,int L,int R,int l,int r)

{

    if(L <= l && r <= R)return t[a].sum + t[b].sum - t[c].sum - t[d].sum;

    register ll res = 0;

    if(L <= mid)res += query(t[a].lc,t[b].lc,t[c].lc,t[d].lc,L,R,l,mid);

    if(R > mid)res += query(t[a].rc,t[b].rc,t[c].rc,t[d].rc,L,R,mid + 1,r);

    return res;

}

ll gcd(ll a,ll b){return (b == 0ll ? a : gcd(b,a % b));}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

    n = read();m = read();

    register int a,b;

    for(register int i = 1;i < n;++i)

    {

        a = read();b = read();

        add(a,b);

    }

    for(register int i = 1;i <= m;++i)

    {

        r[i].fi = read();r[i].se = read();

        g[r[i].fi].push_back(r[i].se);    

    }

    dfs1(1,1);dfs2(1,1);

    build(root[0],1,2 * n);

    efs1(1,0);efs2(1,0);

    register ll ans = 0;

    for(register int i = 1;i <= m;++i)

    {

        register int lca = LCA(r[i].fi,r[i].se);

        register ll x,y,z; 

        x = query(root[r[i].fi],root[r[i].se],root[lca],root[fa[lca]],in[lca],in[r[i].fi],1,tot);

        y = query(root[r[i].fi],root[r[i].se],root[lca],root[fa[lca]],in[lca],in[r[i].se],1,tot);

        z = query(root[r[i].fi],root[r[i].se],root[lca],root[fa[lca]],in[lca],in[lca],1,tot);

        ans += x + y - z - 1;

    }

    sort(r + 1,r + 1 + m);

    for(register int i = 1,j;i <= m;i = j)

    {

        for(j = i + 1;j <= m && r[i] == r[j];++j);

        ans -= (ll)(j - i) * (j - i - 1) / 2;

    }

    register ll res = (ll)m * (m - 1) / 2;

    register ll g = gcd(ans,res);

    ans = ans / g;res = res / g;

    printf("%lld/%lld\n",ans,res);

    return 0;

}