Codeforces Round #528 (Div. 2) D. Minimum Diameter Tree 思维

思维"/>

Codeforces Round #528 (Div. 2) D. Minimum Diameter Tree 思维

题解

题目大意 一个树 让你设定权值要求所有权值和为s 问任意两点间数值和的最大值的最小情况

当权值评分到所有叶子节点上才能保证代价最小 答案为 S / 叶子节点数量 * 2

AC代码

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 10;
int d[MAXN];int main()
{
#ifdef LOCAL//freopen("C:/input.txt", "r", stdin);
#endifint N, S;cin >> N >> S;for (int i = 1; i < N; i++){int a, b;scanf("%d%d", &a, &b);d[a]++, d[b]++;}int cnt = 0;for (int i = 1; i <= N; i++) //统计叶子节点if (d[i] == 1)cnt++;printf("%.10lf\n", 1.0 * S / cnt * 2);return 0;
}