NC220367. H有多短
描述
给定一棵n（2<=n<=100000,n∈Z+）个点的树（保证树连通），将k（0<=k<=1000000000,k∈Z）分配到各个边的权值上，使得每条边权值为A[i]（0<=A[i]<=k,A[i] ∈ R）。现求分配权值后树的直径的最小值。
树的直径：树上最远的两点的路径权值和。
输入描述
n k
接下来的n-1行，每行包括u和v，表示结点u和v相连
2<=n<=100000,n∈Z+
0<=k<=1000000000,k∈Z
1<=u, v<=n, f[i] ∈ Z
输出描述
分配权值后树的直径的最小值，保留6位小数
示例1
输入:
2 10 1 2
输出:
10.000000
说明:
最短情况也是唯一情况，1-2这条边赋予权值10，直径为10
C(clang11) 解法, 执行用时: 30ms, 内存消耗: 632K, 提交时间: 2021-03-28 10:45:37
#include<stdio.h>
int d[100002],n,k;
int main() {
scanf("%d%d",&n,&k);
double num =0 ;
for(int i=1; i<=n-1 ; i++) {
int u,v;
scanf("%d%d",&u,&v);
d[u]++,d[v]++;
}
for(int i=1 ; i<=n ; i++) if(d[i]==1) num = num+1;
double ans = 1.0*k/num*1.0;
printf("%.6lf",ans*2.0);
return 0;
}
C++(clang++11) 解法, 执行用时: 49ms, 内存消耗: 760K, 提交时间: 2021-03-30 15:16:00
#include<bits/stdc++.h>
using namespace std;
int n,s,x,y,rd[100005];
double k;
int main()
{
cin>>n>>k;
for(int i=1;i<n;i++)
{
cin>>x>>y;
rd[x]++; rd[y]++;
}
for(int i=1;i<=n;i++)
if(rd[i]==1) s++;
printf("%.6f",2.0*k/s);
return 0;
}