C - Minimum Diameter Tree
You are given a tree (an undirected connected graph without cycles) and an integer ss.
Vanya wants to put weights on all edges of the tree so that all weights are non-negative real numbers and their sum is ss. At the same time, he wants to make the diameter of the tree as small as possible.
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.
Find the minimum possible diameter that Vanya can get.
Input
The first line contains two integer numbers nn and ss (2 \leq n \leq 10^52≤n≤105, 1 \leq s \leq 10^91≤s≤109) — the number of vertices in the tree and the sum of edge weights.
Each of the following n−1n−1 lines contains two space-separated integer numbers a_iai and b_ibi (1 \leq a_i, b_i \leq n1≤ai,bi≤n, a_i \neq b_iai=bi) — the indexes of vertices connected by an edge. The edges are undirected.
It is guaranteed that the given edges form a tree.
Output
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 ss.
Your answer will be considered correct if its absolute or relative error does not exceed 10^{-6}10−6.
Formally, let your answer be aa, and the jury's answer be bb. Your answer is considered correct if \frac {|a-b|} {max(1, b)} \leq 10^{-6}max(1,b)∣a−b∣≤10−6.
Sample 1
| Inputcopy | Outputcopy |
|---|---|
4 3 1 2 1 3 1 4 | 2.000000000000000000 |
Sample 2
| Inputcopy | Outputcopy |
|---|---|
6 1 2 1 2 3 2 5 5 4 5 6 | 0.500000000000000000 |
Sample 3
| Inputcopy | Outputcopy |
|---|---|
5 5 1 2 2 3 3 4 3 5 | 3.333333333333333333 |
解法：用vector来存储树，然后遍历出叶子节点的个数，用s*2/叶子节点总数，即是使得最短路的最大值最小的非负权边。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>vec[N];
int main(){
int n;
double s;
scanf("%d%lf",&n,&s);
int x,y;
for(int i=1;i<=n-1;i++){
scanf("%d%d",&x,&y),vec[x].push_back(y),vec[y].push_back(x);
}
double sum=0;
for(int i=1;i<=n;i++){
if(vec[i].size()==1)sum+=1;
}
printf("%.10f\n",s*2/sum);
return 0;
}