#P6682. [2019年3月雅礼集训]大树(深度优先版)

    ID: 6532 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000提高树形 DP排序贪心相邻交换确定比较规则

[2019年3月雅礼集训]大树(深度优先版)

本站深度优先版。 历史 PDF 允许在树上自由行走,也未给出宝箱位置的概率分布。现有评测按等概率、深度优先搜索计算,且有评测用例的答案与自由搜索不同。本页明确列出评测使用的规则。原稿保留供查阅。

题目描述

有一棵以点 11 为根、带正整数边权的树。你从根出发,宝箱等概率地放在 2,3,…,n2,3,\ldots,n 中的一个结点。到达该结点时才会发现宝箱。走过一条权值为 ww 的边需要 ww 秒。

搜索必须按深度优先顺序进行。在某结点可以任意选择其尚未搜索的儿子,但一旦进入该儿子的子树,就须搜索完该子树中的所有结点,才可回到父结点搜索其他儿子的子树。在找到宝箱时立即停止。

求所有允许的搜索顺序中,找到宝箱的最小期望时间。

输入格式

第一行一个整数 nn。接下来 n−1n-1 行,每行三个整数 u,v,wu,v,w,表示 u,vu,v 之间有一条权值为 ww 的边。

输出格式

一行一个实数,表示最小期望时间。绝对误差或相对误差不超过 10−610^{-6} 的答案视为正确。

样例

4
1 2 1
1 3 1
3 4 2
3.000

路线 1→2→1→3→41\to2\to1\to3\to4 中,首次到达结点 2,3,42,3,4 的时间分别为 1,3,51,3,5 秒,期望为 33 秒。

数据范围

2≤n≤1052\le n\le10^5,1≤w≤10001\le w\le1000。

测试点 附加条件
1–5 n≤8n\le8
6–7 每个非根结点的父结点都是 11
8–11 每个结点至多有两个儿子
12–20 无

原题作者署名 demerzel。

历史 PDF 题面