1 条题解

  • 0
    @ 2026-1-12 19:44:11

    #include <bits/stdc++.h>
    #define et(i) (e[i].u ^ e[i].v)
    #define Max 170734
    using namespace std;
    
    typedef vector <int> vec;
    
    struct edge{
        int u, v; double c;
        edge *read(){scanf("%d%d%lf", &u, &v, &c); return this;}
    };
    
    int V, inf, sup;
    int i, j, rt, cx;
    edge e[Max];
    vec g[Max];
    // dfs
    int used[Max], sz[Max], f[Max]; // size of tree, Max size of subtree of node
    double l, r, m, ans, bnd;
    // check
    double pfs[Max], depdis[Max]; // prefix sum, max distance of each depth
    int dep[Max], que[Max], Mque[Max];
    
    void getCentroid(int x, int _V, int *cen){
        vec :: iterator it;
        int y;
        sz[x] = 1;
        f[x] = 0;
        used[x] = cx;
        for(it = g[x].begin(); it != g[x].end(); ++it)
            if(0 <= used[y = x ^ et(*it)] && used[y] != cx){
                getCentroid(y, _V, cen);
                sz[x] += sz[y];
                f[x] = max(f[x], sz[y]);
            }
        f[x] = max(f[x], _V - sz[x]);
        if(f[x] < f[*cen]) *cen = x;
    }
    
    bool stcx(int eg0, int eg1){return sz[j ^ et(eg0)] < sz[j ^ et(eg1)];}
    
    bool check(int x, double avg){
        vec :: iterator it, jt;
        int h, t, h0, t0; // two queue 
        int y, z, i; // iterator
        int maxHt = -1, nowHt, unHt; // Max of all height, height of this subtree, allowed union height
        for(it = g[x].begin(); it != g[x].end(); ++it)
            if(used[y = x ^ et(*it)] >= 0){
                que[0] = y; // bfs
                used[y] = cx;
                t = dep[y] = 1;
                pfs[y] = e[*it].c - avg;
                for(h = 0; h < t; h++)
                    for(jt = g[z = que[h]].begin(); jt != g[z].end(); ++jt)
                        if(0 <= used[y = z ^ et(*jt)] && used[y] != cx){ // next node
                            que[t++] = y;
                            used[y] = cx;
                            dep[y] = dep[z] + 1;
                            pfs[y] = pfs[z] + (e[*jt].c - avg);
                        }
                nowHt = dep[que[t - 1]]; // get height of this subtree
                unHt = maxHt;
                h0 = t0 = 1;
                for(i = 0; i < t; i++){
                    for(z = que[i]; unHt >= 0 && dep[z] + unHt >= inf; unHt--){
                        for(; h0 < t0 && depdis[unHt] > depdis[Mque[t0 - 1]]; t0--); // keep the queue disdep[Mque[]] monotone
                        Mque[t0++] = unHt; // insert element
                    }
                    for(; h0 < t0 && Mque[h0] + dep[z] > sup; ++h0); // avoid over upperbound
                    if(h0 < t0 && pfs[z] + depdis[Mque[h0]] > -1e-4) return true; // found a path
                }
                for(i = maxHt + 1; i <= nowHt; i++)
                    depdis[i] = -INFINITY; // initialize
                for(i = 0; i < t; i++)
                    depdis[dep[z = que[i]]] = max(depdis[dep[z]], pfs[z]); // update the max distance of this depth
                maxHt = max(maxHt, nowHt);
            }
        return false; // couldn't find a path
    }
    
    void solve(int x){
        vec :: iterator it;
        int y, i;
        sort(g[j = x].begin(), g[x].end(), stcx);
        used[x] |= INT_MIN;
        ++cx;
        for(l = ans, r = bnd; r - l > 1e-4; ++cx){
            m = (l + r) * 0.5;
            check(x, m) ? l = m : r = m;
        }
        ans = l;
        for(it = g[x].begin(); it != g[x].end(); ++it)
            if(used[y = x ^ et(*it)] >= 0){
                f[rt = 0] = INT_MAX;
                ++cx;
                getCentroid(y, sz[y], &rt);
                if(sz[y] >= inf)
                    solve(rt);
            }
    }
    
    int main(){
        scanf("%d%d%d", &V, &inf, &sup);
        ans = 0.0;
        bnd = -INFINITY;
        for(i = 0; i < V - 1; i++){
            e[i].read();
            bnd = max(bnd, e[i].c);
            g[e[i].u].push_back(i);
            g[e[i].v].push_back(i);
        }
        f[rt = 0] = INT_MAX;
        cx = 1;
        getCentroid(1, V, &rt);
        solve(rt);
        printf("%.3lf\n", ans);
        return 0;
    }
    
    
    • 1

    信息

    ID
    3414
    时间
    4000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    1
    上传者