11064번: Diameter

https://www.acmicpc.net/problem/11064

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int t, n, d;
int main() {
    for (scanf("%d", &t); t--;) {
        vector<pair<int, int> > adj[40001];
        priority_queue<pair<int, int> > pq;
        int r = 0, t = 0, cnt = 0, ind[40001] = {};
        scanf("%d%d", &n, &d);
        for (int i = 1, x, y, z; i < n; i++) {
            scanf("%d%d%d", &x, &y, &z);
            adj[x].push_back({ y,z });
            adj[y].push_back({ x,z });
            r += z;
            ind[x]++;
            ind[y]++;
        }
        for (int i = 1; i <= n; i++) if (ind[i] == 1) pq.push({ -adj[i][0].second,i }), cnt++;
        for (;;) {
            int h = pq.top().second, dis = -pq.top().first;
            pq.pop();
            if (2 * dis >= d) {
                printf("%.1lf\n", r - (d / 2.0 - t) * cnt);
                break;
            }
            r -= (dis - t)*cnt--;
            if (cnt == 1) {
                puts("0.0");
                break;
            }
            ind[h]--;
            for (auto u : adj[h]) if (--ind[u.first] == 1) {
                for (auto v : adj[u.first]) if (ind[v.first]) pq.push({ -dis - v.second,u.first }), cnt++;
            }
            t = dis;
        }
    }
    return 0;
}