codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1085D.md (2377B)


      1 Source: https://codeforces.com/problemset/problem/1085/D
      2 
      3 D. Minimum Diameter Tree
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a tree (an undirected connected graph without cycles) and an integer $s$.
     22 
     23 Vanya wants to put weights on all edges of the tree so that all weights are non-negative real numbers and their sum is $s$. At the same time, he wants to make the diameter of the tree as small as possible.
     24 
     25 Let's define the diameter of a weighed tree as the maximum sum of the weights of the edges lying on the path between two some vertices of the tree. In other words, the diameter of a weighed tree is the length of the longest simple path in the tree, where length of a path is equal to the sum of weights over all edges in the path.
     26 
     27 Find the minimum possible diameter that Vanya can get.
     28 
     29 Input
     30 
     31 The first line contains two integer numbers $n$ and $s$ ($2 \leq n \leq 10^5$, $1 \leq s \leq 10^9$) — the number of vertices in the tree and the sum of edge weights.
     32 
     33 Each of the following $nāˆ’1$ lines contains two space-separated integer numbers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — the indexes of vertices connected by an edge. The edges are undirected.
     34 
     35 It is guaranteed that the given edges form a tree.
     36 
     37 Output
     38 
     39 Print the minimum diameter of the tree that Vanya can get by placing some non-negative real weights on its edges with the sum equal to $s$.
     40 
     41 Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.
     42 
     43 Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $\frac {|a-b|} {max(1, b)} \leq 10^{-6}$.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 4 3
     51 1 2
     52 1 3
     53 1 4
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 2.000000000000000000
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 6 1
     66 2 1
     67 2 3
     68 2 5
     69 5 4
     70 5 6
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 0.500000000000000000
     77 ```
     78 
     79 Input
     80 
     81 ```
     82 5 5
     83 1 2
     84 2 3
     85 3 4
     86 3 5
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 3.333333333333333333
     93 ```
     94 
     95 Note
     96 
     97 In the first example it is necessary to put weights like this:
     98 
     99  ![](https://espresso.codeforces.com/3c45ad7e8b5b86e354c87c2434e3c142ecc81a86.png) 
    100 
    101 It is easy to see that the diameter of this tree is $2$. It can be proved that it is the minimum possible diameter.
    102 
    103 In the second example it is necessary to put weights like this:
    104 
    105  ![](https://espresso.codeforces.com/0b658c854c315839df5e419167f44d5ed78427a8.png)