English · Original
Chinese · Translation
Formal · Original
Gerald is positioned in an old castle which consists of _n_ halls connected with _n_ - 1 corridors. It is exactly one way to go from any hall to any other one. Thus, the graph is a tree. Initially, at the moment of time 0, Gerald is positioned in hall 1. Besides, some other hall of the castle contains the treasure Gerald is looking for. The treasure's position is not known; it can equiprobably be in any of other _n_ - 1 halls. Gerald can only find out where the treasure is when he enters the hall with the treasure. That very moment Gerald sees the treasure and the moment is regarded is the moment of achieving his goal.
The corridors have different lengths. At that, the corridors are considered long and the halls are considered small and well lit. Thus, it is possible not to take the time Gerald spends in the halls into consideration. **The castle is very old, that's why a corridor collapses at the moment when somebody visits it two times, no matter in which direction.**
Gerald can move around the castle using the corridors; he will go until he finds the treasure. Naturally, Gerald wants to find it as quickly as possible. In other words, he wants to act in a manner that would make the average time of finding the treasure as small as possible. **Each corridor can be used no more than two times. That's why Gerald chooses the strategy in such a way, so he can visit every hall for sure.**
More formally, if the treasure is located in the second hall, then Gerald will find it the moment he enters the second hall for the first time — let it be moment _t_2. If the treasure is in the third hall, then Gerald will find it the moment he enters the third hall for the first time. Let it be the moment of time _t_3. And so on. Thus, the average time of finding the treasure will be equal to .
## Input
The first line contains the only integer _n_ (2 ≤ _n_ ≤ 105) — the number of halls in the castle. Next _n_ - 1 lines each contain three integers. The _i_\-th line contains numbers _a__i_, _b__i_ and _t__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_, _a__i_ ≠ _b__i_, 1 ≤ _t__i_ ≤ 1000) — the numbers of halls connected with the _i_\-th corridor and the time needed to go along the corridor. Initially Gerald is in the hall number 1. It is guaranteed that one can get from any hall to any other one using corridors.
## Output
Print the only real number: the sought expectation of time needed to find the treasure. The answer should differ from the right one in no less than 10 - 6.
[samples]
## Note
In the first test the castle only has two halls which means that the treasure is located in the second hall. Gerald will only need one minute to go to the second hall from the first one.
In the second test Gerald can only go from the first hall to the third one. He can get from the third room to the first one or to the second one, but he has already visited the first hall and can get nowhere from there. Thus, he needs to go to the second hall. He should go to hall 4 from there, because all other halls have already been visited. If the treasure is located in the third hall, Gerald will find it in a minute, if the treasure is located in the second hall, Gerald finds it in two minutes, if the treasure is in the fourth hall, Gerald will find it in three minutes. The average time makes 2 minutes.
In the third test Gerald needs to visit 4 halls: the second, third, fourth and fifth ones. All of them are only reachable from the first hall. Thus, he needs to go to those 4 halls one by one and return. Gerald will enter the first of those halls in a minute, in the second one — in three minutes, in the third one - in 5 minutes, in the fourth one - in 7 minutes. The average time is 4 minutes.
Gerald 位于一座由 #cf_span[n] 个大厅和 #cf_span[n - 1] 条走廊连接的古老城堡中。任意两个大厅之间有且仅有一条路径相连，因此该图是一棵树。初始时刻（时间 #cf_span[0]），Gerald 位于大厅 #cf_span[1]。此外，城堡中另一个大厅藏有 Gerald 寻找的宝藏，宝藏的位置未知，等概率地分布在其余 #cf_span[n - 1] 个大厅中的任意一个。Gerald 只有在进入藏有宝藏的大厅时才能发现宝藏，此时即为他达成目标的时刻。
走廊具有不同的长度。由于走廊较长而大厅较小且照明良好，因此可以忽略 Gerald 在大厅内花费的时间。*城堡年代久远，一旦某条走廊被经过两次（无论方向），就会坍塌。*
Gerald 可以通过走廊在城堡中移动，直到找到宝藏。显然，他希望尽可能快地找到宝藏，即最小化找到宝藏的平均时间。*每条走廊最多只能使用两次。因此，Gerald 选择的策略必须确保他能访问所有大厅。*
更正式地，如果宝藏位于第二个大厅，则 Gerald 在首次进入第二个大厅时发现它——设该时刻为 #cf_span[t2]。如果宝藏位于第三个大厅，则 Gerald 在首次进入第三个大厅时发现它，设该时刻为 #cf_span[t3]，依此类推。因此，找到宝藏的平均时间为 。
第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105]) —— 城堡中大厅的数量。接下来 #cf_span[n - 1] 行，每行包含三个整数。第 #cf_span[i] 行包含数字 #cf_span[ai], #cf_span[bi] 和 #cf_span[ti] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[ai ≠ bi], #cf_span[1 ≤ ti ≤ 1000]) —— 表示第 #cf_span[i] 条走廊连接的两个大厅编号及通过该走廊所需的时间。Gerald 初始位于大厅 #cf_span[1]。保证任意两个大厅之间可以通过走廊相互到达。
请输出一个实数：找到宝藏所需时间的期望值。答案与正确值的误差不得超过 #cf_span[10 - 6]。
在第一个测试用例中，城堡仅有两个大厅，因此宝藏位于第二个大厅。Gerald 仅需一分钟即可从第一个大厅到达第二个大厅。
在第二个测试用例中，Gerald 只能从第一个大厅前往第三个大厅。他可以从第三个大厅返回第一个大厅或前往第二个大厅，但第一个大厅已被访问过，无法再从那里继续前进。因此，他必须前往第二个大厅。由于其他所有大厅都已访问过，他应从第二个大厅前往第四个大厅。如果宝藏位于第三个大厅，Gerald 将在 1 分钟时发现它；如果宝藏位于第二个大厅，Gerald 将在 2 分钟时发现它；如果宝藏位于第四个大厅，Gerald 将在 3 分钟时发现它。平均时间为 #cf_span[2] 分钟。
在第三个测试用例中，Gerald 需要访问 #cf_span[4] 个大厅：第二个、第三个、第四个和第五个。它们都仅能从第一个大厅到达。因此，他必须依次前往这些大厅并返回。Gerald 将在第 1 分钟进入第一个大厅，第 3 分钟进入第二个大厅，第 #cf_span[5] 分钟进入第三个大厅，第 #cf_span[7] 分钟进入第四个大厅。平均时间为 #cf_span[4] 分钟。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105]) —— 城堡中大厅的数量。接下来 #cf_span[n - 1] 行，每行包含三个整数。第 #cf_span[i] 行包含数字 #cf_span[ai], #cf_span[bi] 和 #cf_span[ti] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[ai ≠ bi], #cf_span[1 ≤ ti ≤ 1000]) —— 表示第 #cf_span[i] 条走廊连接的两个大厅编号及通过该走廊所需的时间。Gerald 初始位于大厅 #cf_span[1]。保证任意两个大厅之间可以通过走廊相互到达。
## Output
请输出一个实数：找到宝藏所需时间的期望值。答案与正确值的误差不得超过 #cf_span[10 - 6]。
[samples]
## Note
在第一个测试用例中，城堡仅有两个大厅，因此宝藏位于第二个大厅。Gerald 仅需一分钟即可从第一个大厅到达第二个大厅。在第二个测试用例中，Gerald 只能从第一个大厅前往第三个大厅。他可以从第三个大厅返回第一个大厅或前往第二个大厅，但第一个大厅已被访问过，无法再从那里继续前进。因此，他必须前往第二个大厅。由于其他所有大厅都已访问过，他应从第二个大厅前往第四个大厅。如果宝藏位于第三个大厅，Gerald 将在 1 分钟时发现它；如果宝藏位于第二个大厅，Gerald 将在 2 分钟时发现它；如果宝藏位于第四个大厅，Gerald 将在 3 分钟时发现它。平均时间为 #cf_span[2] 分钟。在第三个测试用例中，Gerald 需要访问 #cf_span[4] 个大厅：第二个、第三个、第四个和第五个。它们都仅能从第一个大厅到达。因此，他必须依次前往这些大厅并返回。Gerald 将在第 1 分钟进入第一个大厅，第 3 分钟进入第二个大厅，第 #cf_span[5] 分钟进入第三个大厅，第 #cf_span[7] 分钟进入第四个大厅。平均时间为 #cf_span[4] 分钟。
**Definitions**
Let $ n \in \mathbb{Z} $, $ n \geq 2 $, be the number of halls.
Let $ T = (V, E) $ be a tree with vertex set $ V = \{1, 2, \dots, n\} $, where hall $ 1 $ is the root (Gerald’s starting position).
Each edge $ e = (u, v) \in E $ has a positive integer weight $ w(e) \in \mathbb{Z}^+ $, representing the time to traverse the corridor.
Let $ \mathcal{P} $ be the set of all possible depth-first traversal strategies starting at hall $ 1 $, such that every vertex is visited exactly once (due to corridor collapse on second use, Gerald must traverse each edge at most twice — once in each direction — but each vertex is entered only once for treasure detection).
Since the tree is undirected and Gerald cannot revisit any corridor after two traversals, the only feasible strategy is a **depth-first search (DFS)** that explores the tree without backtracking unnecessarily — i.e., each subtree is explored in full before returning, and the order of visiting children matters.
The treasure is uniformly distributed among the $ n-1 $ halls $ \{2, 3, \dots, n\} $.
Let $ t(v) $ denote the time at which Gerald first enters hall $ v $ under a given DFS strategy.
**Constraints**
1. $ 2 \leq n \leq 10^5 $
2. The graph is a tree with $ n-1 $ edges.
3. Each corridor has weight $ w(e) \in [1, 1000] $.
4. Gerald starts at hall $ 1 $ at time $ 0 $.
5. Each corridor can be traversed at most twice (once in each direction), but each hall is entered only once for treasure detection.
6. The strategy must guarantee visiting all halls.
**Objective**
Minimize the expected time to find the treasure:
$$
\mathbb{E}[T] = \frac{1}{n-1} \sum_{v=2}^{n} t(v)
$$
where $ t(v) $ is the first-visit time to hall $ v $ under an optimal DFS traversal order (i.e., the order of visiting children at each node is chosen to minimize the above expectation).
The optimal strategy is to order the children of each node by increasing **expected contribution** — specifically, for each subtree rooted at a child $ c $ of node $ u $, the cost of visiting the entire subtree is proportional to the sum of edge weights in the subtree multiplied by 2 (for round-trip), and the first-visit time to nodes in the subtree is delayed by the traversal time to reach $ c $.
Thus, the optimal DFS order at each node is to visit children in **increasing order of the total weight of their subtree** (i.e., the sum of edge weights in the subtree rooted at that child).
Let $ \text{subtree\_weight}(v) $ be the sum of weights of all edges in the subtree rooted at $ v $ (including the edge from parent to $ v $).
Then, the expected time is computed recursively:
For each node $ u $, let $ C(u) $ be its children. Sort $ C(u) $ by $ \text{subtree\_weight}(c) $ in increasing order.
Let $ \text{time}(u) $ be the time when Gerald arrives at $ u $.
Then, for each child $ c_i $ in sorted order:
- $ t(c_i) = \text{time}(u) + w(u, c_i) $
- $ \text{time}(c_i) = t(c_i) + 2 \cdot \text{subtree\_weight}(c_i) $
The total expectation is:
$$
\boxed{\frac{1}{n-1} \sum_{v=2}^{n} t(v)}
$$
computed via DFS with optimal child ordering by subtree weight.
API Response (JSON)
{
"problem": {
"name": "D. Castle",
"description": {
"content": "Gerald is positioned in an old castle which consists of _n_ halls connected with _n_ - 1 corridors. It is exactly one way to go from any hall to any other one. Thus, the graph is a tree. Initially, at",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF101D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Gerald is positioned in an old castle which consists of _n_ halls connected with _n_ - 1 corridors. It is exactly one way to go from any hall to any other one. Thus, the graph is a tree. Initially, at...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Gerald 位于一座由 #cf_span[n] 个大厅和 #cf_span[n - 1] 条走廊连接的古老城堡中。任意两个大厅之间有且仅有一条路径相连，因此该图是一棵树。初始时刻（时间 #cf_span[0]），Gerald 位于大厅 #cf_span[1]。此外，城堡中另一个大厅藏有 Gerald 寻找的宝藏，宝藏的位置未知，等概率地分布在其余 #cf_span[n - 1] 个大厅中的任意一...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 2 $, be the number of halls. \nLet $ T = (V, E) $ be a tree with vertex set $ V = \\{1, 2, \\dots, n\\} $, where hall $ 1 $ is the root (Gerald’s star...",
"is_translate": false,
"language": "Formal"
}
]
}