TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4899
  • 题目
  • P4899精神污染
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,64m
    问题描述

    兵库县位于日本列岛的中央位置,北临日本海,南面濑户内海直通太平洋,中央部位是森林和山地,与拥有关西机场的大阪府比邻而居,是关西地区面积最大的县,是集经济和文化于一体的一大地区,是日本西部门户,海陆空交通设施发达。濑户内海沿岸气候温暖,多晴天,有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市,还有以疗养地而闻名的六甲山地等。

    兵库县官方也大力发展旅游,为了方便,他们在县内的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

    提示

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

    样例解释

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


    来源  bzoj 3772