第十集 原来这一切都是真的

TimeLimit:1000MS  MemoryLimit:128MB
64-bit integer IO format:%lld
Special Judge
未提交 | 登录后收藏
Problem Description

    原来小C的身上被安装了窃听器,他们以前的所有谈话都被她父亲窃听了。当他们知晓了宝藏位置之后,就被他父亲的特工抓走。

    “头好晕啊~~这是哪里?”小A晕沉沉地醒来。这是一间密室,小A被锁在里面。“有没有人呀?放我出去!”,他大叫到。

    “父亲,求你放过他吧,我求求你了!”小C苦苦央求。“我从小怎么教你的?男人都不是好东西,除了你爸我!”,他不屑地骂到。“如果你要杀他,把我也杀了吧!”,小C气愤地说。他爸更不屑一顾地说道“哟哟哟,你当这是在演电视剧哦?还琼瑶浪漫桥段哦!我告诉你,不可能!反正你不是我亲生的!”。“爸,你说什么?我真的不是你亲生的?难道是隔壁老王的?”,小C震惊地问。“你说的对!你已经长大了,我没有什么好隐瞒你了!之所以那样,我才把你母亲杀了!”,父亲变态地说着。“你不是人!”,在小C夺门而出,她无法想象,原来一切会是这样的。

她想去救小A,就偷偷潜入密室。关小A的密室是在最里面,从密室的门口通往外面大门口要通过好多个路口,密室、每个路口、和大门都有一个编号,其中0编号是关小A的密室,因为老大是学计算机的。密室通向多个路口,每个路口都可能有多个支路,最终通向多个大门,但是它们不会形成环路而迷路。
   
每个大门最多有一个守卫且没有守卫的概率是大门的编号占总编号的百分比(编号为i的大门没有守卫的概率是i/nn表示路口密室和大门的总个数,即编号的个数),到了每个路口,如果与这个路口相邻的靠外边的路口或大门的守卫个数总和为奇数的话,这个路口就应该有一个守卫。至于为何这样因为小C本是内部人员所以才能知晓。现在小C想知道关小A的密室没有守卫的概率是多少。现在小A不在身边,所以你们要帮助她!帮她救出小A,才能够AC,对吧?

广告时间:“全剧组”提醒你,本集是第一季最后一集了,至于本集里面为何守卫要如此复杂地安排,我们就不解释了,你们猜!AC的故事还没结束哦!欢迎明年继续参加校赛哈!

你们果然不负所望轻松解决了这道难题,帮助小C找到了小A

“你跟我走!”小C小声地说。“你为什么要救我,你快走,被发现你就死定了!”小A不忍她受到伤害。“要死一起死!”小C坚定地拉着他的手逃出来。

由于小C熟悉地形,所以他们成功地私奔了。

C父亲知道后非常生气,就派他的特工追杀他们。“你们去!把他们都杀了!”他生气地喊道。“可是,你女儿?”特工领头人疑惑地问。

“她不是我女儿,你们追上把她一起杀了!”他一拍桌子,文件散落一地。

   

 

Input

 第一行是t表示测试数据的数量

每组数据第一行是n表示大门、路口、密室的总数。(1个密室,多个路口和大门)(2<=n<=100000)
其中密室的编号为0,大门和路口的编号是1 ~ n-1。
接下来n-1行,每行有两个数字a和b 表示编号为a的地方和编号为b的地方是联通的(自行判断那些是大门,哪些是路口)。输入的数据保证会满足题目所说的条件
Output

 输出密室没有守卫的概率,保留6位小数,如果输出和标准答案的差不超过0.0001则视为正确答案

SampleInput
1
4
0 1
0 2
2 3
SampleOutput
0.375000
Submit
题目统计信息详细
总AC数4
通过人数2
尝试人数4
总提交量12
AC率16.67%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: