【BZOJ 1758】【WC 2010】重建计划 分数规划+点分治+单调队列

一开始看到$\frac{\sum_{}}{\sum_{}}$就想到了01分数规划但最终还是看了题解

二分完后的点分治，只需要维护一个由之前处理过的子树得出的$tb数组$，然后根据遍历每个当前的子树上的结点的深度来确定$tb数组$中的滑块。

因为分数规划要找的是$max$，BFS遍历当前结点的深度越来越大，这样滑块也是单调向右滑动，所以滑块里的最大值就应当用单调队列解决

#include<cstdio>

#include<algorithm>

#define read(x) x=getint()

#define N 100003

#define eps 0.0001

#define max(a,b) (a)>(b)?a:b

using namespace std;

inline int getint() {

    char c; int fh = 1, k = 0;

    for( ; c < '0' || c > '9'; c = getchar()) if ( c == '-') fh = -1;

    for( ; c >= '0' && c <= '9'; c = getchar()) k = k * 10 + c - '0';

    return k * fh;

}

struct node {

    int nxt, to, w;

} E[N << 1];

bool vis[N];

double ans = 0.0, limi = 0.0, dis[N], tb[N];

int sz[N], n, cnt = 0, L, U, point[N], root, rtm = N, fa[N], q[N], dq[N], deep[N];

inline void ins( int x, int y, int z) {++cnt; E[cnt].nxt = point[x]; E[cnt].to = y; E[cnt].w = z; point[x] = cnt;}

inline void fdrt( int x, int fa, int s) {

    sz[x] = 1;

    int ma = 0;

    for( int tmp = point[x]; tmp; tmp = E[tmp].nxt)

        if ( !vis[E[tmp].to] && E[tmp].to != fa) {

            fdrt( E[tmp].to, x, s);

            sz[x] += sz[E[tmp].to];

            ma = max( ma, sz[E[tmp].to]);

        }

    ma = max( ma, s - ma);

    if ( ma < rtm) {

        rtm = ma;

        root = x;

    }

}

inline bool can( int x, double M) {

    int le = 0, head, tail, h, t, now;

    for( int tmp = point[x]; tmp; tmp = E[tmp].nxt)

        if ( !vis[E[tmp].to]) {

            head = 0;

            tail = 1;

            q[0] = E[tmp].to;

            fa[E[tmp].to] = x;

            deep[E[tmp].to] = 1;

            dis[E[tmp].to] = (double) E[tmp].w - M;

            while ( head != tail) {

                now = q[head];

                ++head; if ( head >= N) head %= N;

                for( int i = point[now]; i; i = E[i].nxt)

                    if ( !vis[E[i].to] && E[i].to != fa[now]) {

                        q[tail] = E[i].to;

                        fa[E[i].to] = now;

                        deep[E[i].to] = deep[now] + 1;

                        dis[E[i].to] = dis[now] + (double) E[i].w - M;

                        ++tail; if ( tail >= N) tail %= N;

                    }

            }

            h = 1;

            t = 0;

            now = le;

            for( int i = 0; i < tail; ++i) {

                while ( deep[q[i]] + now >= L && now >= 0) {

                    while ( h <= t && tb[dq[t]] < tb[now])

                        --t;

                    dq[++t] = now;

                    --now;

                }

                while ( h <= t && deep[q[i]] + dq[h] > U)

                    ++h;

                if ( h <= t && dis[q[i]] + tb[dq[h]] >= 0)

                    return 1;

            }

            for( int i = le + 1; i <= deep[q[tail-1]]; ++i)

                tb[i] = -1E9;

            for( int i = 0; i < tail; ++i)

                tb[deep[q[i]]] = max( tb[deep[q[i]]], dis[q[i]]);

            le = max( le, deep[q[tail-1]]);

        }

    return 0;

}

inline void work( int x) {

    double left = ans, right = limi, mid;

    while ( right - left > eps) {

        mid = ( left + right) / 2;

        if ( can ( x, mid))

            left = mid;

        else

            right = mid;

    }

    ans = left;

}

inline void dfs( int x, int s) {

    vis[x] = 1;

    work( x);

    for( int tmp = point[x]; tmp; tmp = E[tmp].nxt)

        if ( !vis[E[tmp].to]) {

            rtm = N;

            int ss = sz[E[tmp].to] < sz[x] ? sz[E[tmp].to] : s - sz[x];

            fdrt( E[tmp].to, -1, ss);

            if ( sz[E[tmp].to] > L)

                dfs( root, ss);

        }

}

int main() {

    read(n); read(L); read(U);

    int a, b, c;

    for( int i = 1; i < n; ++i) {

        read(a); read(b); read(c);

        ins( a, b, c);

        ins( b, a, c);

        limi = max( limi, c);

    }

    fdrt( 1, -1, n);

    dfs( 1, n);

    printf( "%.3lf\n", ans);

    return 0;

}

这样就可以了