C. Journey

Codeforces

IDCF839C

Time2000ms

Memory256MB

Difficulty—

dfs and similardpgraphsprobabilitiestrees

English · Original

Chinese · Translation

There are _n_ cities and _n_ - 1 roads in the Seven Kingdoms, each road connects two cities and we can reach any city from any other by the roads. Theon and Yara Greyjoy are on a horse in the first city, they are starting traveling through the roads. But the weather is foggy, so they can’t see where the horse brings them. When the horse reaches a city (including the first one), it goes to one of the cities connected to the current city. But it is a strange horse, it only goes to cities in which they weren't before. In each such city, the horse goes with equal probabilities and it stops when there are no such cities. Let the length of each road be 1. The journey starts in the city 1. What is the expected length (expected value of length) of their journey? You can read about expected (average) value by the link [https://en.wikipedia.org/wiki/Expected_value](https://en.wikipedia.org/wiki/Expected_value). ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 100000) — number of cities. Then _n_ - 1 lines follow. The _i_\-th line of these lines contains two integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, _u__i_ ≠ _v__i_) — the cities connected by the _i_\-th road. It is guaranteed that one can reach any city from any other by the roads. ## Output Print a number — the expected length of their journey. The journey starts in the city 1. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6. Namely: let's assume that your answer is _a_, and the answer of the jury is _b_. The checker program will consider your answer correct, if . [samples] ## Note In the first sample, their journey may end in cities 3 or 4 with equal probability. The distance to city 3 is 1 and to city 4 is 2, so the expected length is 1.5. In the second sample, their journey may end in city 4 or 5. The distance to the both cities is 2, so the expected length is 2.

在七王国中，有 #cf_span[n] 座城市和 #cf_span[n - 1] 条道路，每条道路连接两座城市，且从任意一座城市都可以通过道路到达其他任意城市。 Theon 和 Yara Greyjoy 骑着马从第一座城市出发，开始沿着道路旅行。但天气多雾，他们无法看清马将带他们去往何处。当马到达一座城市时（包括起点），它会随机选择一条通往尚未访问过的相邻城市的道路前进。这是一匹奇怪的马，它只前往从未去过的城市。在所有满足条件的城市中，马选择每一条道路的概率相等，当没有未访问过的相邻城市时，旅程停止。每条道路的长度为 #cf_span[1]。旅程从城市 #cf_span[1] 开始。求他们旅程的期望长度（即长度的期望值）？有关期望（平均）值的定义，请参阅链接 https://en.wikipedia.org/wiki/Expected_value。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）— 城市的数量。接下来 #cf_span[n - 1] 行，第 #cf_span[i] 行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]，#cf_span[ui ≠ vi]），表示第 #cf_span[i] 条道路连接的两座城市。保证任意两座城市之间都可以通过道路互相到达。请输出一个数 —— 他们旅程的期望长度。旅程从城市 #cf_span[1] 开始。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。即：假设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，若满足，则评测程序将判定你的答案正确。在第一个样例中，他们的旅程可能以城市 #cf_span[3] 或 #cf_span[4] 结束，概率相等。到城市 #cf_span[3] 的距离为 #cf_span[1]，到城市 #cf_span[4] 的距离为 #cf_span[2]，因此期望长度为 #cf_span[1.5]。在第二个样例中，他们的旅程可能以城市 #cf_span[4] 或 #cf_span[5] 结束。到这两座城市的距离均为 #cf_span[2]，因此期望长度为 #cf_span[2]。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）— 城市的数量。接下来 #cf_span[n - 1] 行，第 #cf_span[i] 行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]，#cf_span[ui ≠ vi]），表示第 #cf_span[i] 条道路连接的两座城市。保证任意两座城市之间都可以通过道路互相到达。 ## Output 请输出一个数 —— 他们旅程的期望长度。旅程从城市 #cf_span[1] 开始。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。即：假设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，若满足，则评测程序将判定你的答案正确。 [samples] ## Note 在第一个样例中，他们的旅程可能以城市 #cf_span[3] 或 #cf_span[4] 结束，概率相等。到城市 #cf_span[3] 的距离为 #cf_span[1]，到城市 #cf_span[4] 的距离为 #cf_span[2]，因此期望长度为 #cf_span[1.5]。在第二个样例中，他们的旅程可能以城市 #cf_span[4] 或 #cf_span[5] 结束。到这两座城市的距离均为 #cf_span[2]，因此期望长度为 #cf_span[2]。

Samples

Input #1

Output #1

1.500000000000000

Input #2

Output #2

2.000000000000000

API Response (JSON)

{
  "problem": {
    "name": "C. Journey",
    "description": {
      "content": "There are _n_ cities and _n_ - 1 roads in the Seven Kingdoms, each road connects two cities and we can reach any city from any other by the roads. Theon and Yara Greyjoy are on a horse in the first c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF839C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ cities and _n_ - 1 roads in the Seven Kingdoms, each road connects two cities and we can reach any city from any other by the roads.\n\nTheon and Yara Greyjoy are on a horse in the first c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在七王国中，有 #cf_span[n] 座城市和 #cf_span[n - 1] 条道路，每条道路连接两座城市，且从任意一座城市都可以通过道路到达其他任意城市。\n\nTheon 和 Yara Greyjoy 骑着马从第一座城市出发，开始沿着道路旅行。但天气多雾，他们无法看清马将带他们去往何处。当马到达一座城市时（包括起点），它会随机选择一条通往尚未访问过的相邻城市的道路前进。这是一匹奇怪的马，它只前...",
      "is_translate": true,
      "language": "Chinese"
    }
  ]
}

Full JSON Raw Segments