#P6682. [2019年3月雅礼集训]大树(深度优先版)
[2019年3月雅礼集训]大树(深度优先版)
本站深度优先版。 历史 PDF 允许在树上自由行走,也未给出宝箱位置的概率分布。现有评测按等概率、深度优先搜索计算,且有评测用例的答案与自由搜索不同。本页明确列出评测使用的规则。原稿保留供查阅。
题目描述
有一棵以点 为根、带正整数边权的树。你从根出发,宝箱等概率地放在 中的一个结点。到达该结点时才会发现宝箱。走过一条权值为 的边需要 秒。
搜索必须按深度优先顺序进行。在某结点可以任意选择其尚未搜索的儿子,但一旦进入该儿子的子树,就须搜索完该子树中的所有结点,才可回到父结点搜索其他儿子的子树。在找到宝箱时立即停止。
求所有允许的搜索顺序中,找到宝箱的最小期望时间。
输入格式
第一行一个整数 。接下来 行,每行三个整数 ,表示 之间有一条权值为 的边。
输出格式
一行一个实数,表示最小期望时间。绝对误差或相对误差不超过 的答案视为正确。
样例
4
1 2 1
1 3 1
3 4 2
3.000
路线 中,首次到达结点 的时间分别为 秒,期望为 秒。
数据范围
,。
| 测试点 | 附加条件 |
|---|---|
| 1–5 | |
| 6–7 | 每个非根结点的父结点都是 |
| 8–11 | 每个结点至多有两个儿子 |
| 12–20 | 无 |
原题作者署名 demerzel。