Nowcoder H. 有多短

题意

给定一棵n（2<=n<=100000,n∈Z+）个点的树（保证树连通），将k（0<=k<=1000000000,k∈Z）分配到各个边的权值上，使得每条边权值为A[i]（0<=A[i]<=k,A[i] ∈ R）。现求分配权值后树的直径的最小值。
树的直径：树上最远的两点的路径权值和。
思路

树的直径一定是两个叶子之间的路径 (叶子是树中度数为 $1$ 的点)

贪心策略：为了使得直径最小，最优解是将 $k$ 均摊给与叶子相连的边上,其他边全部赋值为 $0$
（因为树的直径必走两次叶子与其他节点连的边，那么其余类型的边全为0是最优的）

设度数为 $1$ 的点有 $c n t$ 个,那么答案为 $2 ? k / c n t$ ,乘2是因为直径会经过两个被赋值的边

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;

signed main()
{
    IOS;
    int n, k;
    cin >> n >> k;
    vector<int> deg(n + 1);
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
    }

    int cnt = count(deg.begin() + 1, deg.end(), 1);

    printf("%.6lf", 2.0 * k / cnt);
    return 0;
}