WC2010 重建计划

题目:

   X国遭受了地震的重创, 导致全国的交通近乎瘫痪,重建家园的计划迫在眉睫。 X国由个城市组成, 重建小组提出,仅需建立条道路即可使得任意两个城市互相可达。
   于是,重建小组很快提出了一个包含条道路的方案, 并满足城市之间两两可达,他们还计算评估了每条道路建设之后可以带来的价。由于重建计划复杂而艰难,经费也有一定限制。
   因此,政府要求第一期重建工程修建的道路数目为条, 但需满足, 即不应少于条,但不超过条。同时,为了最大化利用率,要求建设的这些道路恰好组成一条简单路径,即所建设的条路径可以构成一个排列, 对于 , 有
   重建小组打算修改他们的原有方案以满足要求,即在原有的条道路中寻找一条路径作为新的方案,使得新方案中的道路平均价值:最大。
   这里表示道路的价值, 表示新方案中道路的条数。
   请你帮助重建小组寻找一个最优方案。注: 在本题中的设置将保证有解。

思路:

   果然自己还是不大行,只能写 的大暴力......
   先大致的讲一下 的做法吧,首先对于平均值最大,比较套路的做法就是去二分平均值。
   如果 ,那么 。问题也就转化成了求树上一条长度在 之间的权值和最大路径。这个可以用线段树和树上启发式合并实现,大致就是用线段树维护每个深度对应的最大权值,然后 保证路径是一条简单路径。
   接下来就到了正解的部分了,二分还是不变的。注意到切分中有一档链可以用单调队列实现,那就考虑能不能把线段树变成单调队列。因为 维护的是到根的信息,在这里不好实现,所以改用点分治。现在对于重心的 个儿子,每次把前 个儿子的信息用单调队列维护,然后去更新第 个儿子。如果设 表示第 个儿子子树中的最大深度,那么这么做的复杂度就是 接近 ,但是如果让 升序排列,这个表达式的值就是 级别的。这样点分治的复杂度就能保证在 ,再加上外面的二分复杂度大概是 (然而这么神奇的排序我是搞不来的,模拟赛的时候大暴力卡卡就过了)

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 100005;
const db eps = 1e-8;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
struct Edge {
    int to, w;
};
Link<N, N * 2, Edge> G;

int n, D, U, siz[N];
bool mark[N];
void dfs_anc(int o, int f, int all, int &mn, int &rt) {
    siz[o] = 1; int now = 0;
    erep(k, G, o) {
        int v = G[k].to;
        if(v == f || mark[v]) continue;
        dfs_anc(v, o, all, mn, rt);
        siz[o] += siz[v];
        tomax(now, siz[v]);
    }
    tomax(now, all - siz[o]);
    if(tomin(mn, now)) rt = o;
}
int dfs_mx(int o, int f) {
    int mx = 0;
    erep(k, G, o) {
        int v = G[k].to;
        if(v == f || mark[v]) continue;
        tomax(mx, dfs_mx(v, o));
    }
    return mx + 1;
}
struct Data {
    int id, val, len;
    bool operator< (const Data d) const {
        return val < d.val;
    }
} data[N];
int tot, que[N], dep[N], tag[N], dq[N];
db ans, dis[N], mx[N];
bool check(int x, db now) {
    static int cur_time = 0;
    tag[x] = ++cur_time; mx[0] = 0;
    int mx_dep = 0;
    rep(i, 1, tot) {
        int v = data[i].id, hed = 1, tai = 0;
        dis[v] = data[i].len - now; dep[v] = 1; 
        que[++tai] = v; tag[v] = cur_time;
        while(hed <= tai) {
            int o = que[hed++];
            erep(k, G, o) {
                int t = G[k].to;
                if(!mark[t] && tag[t] != cur_time) {
                    tag[t] = cur_time;
                    que[++tai] = t;
                    dis[t] = dis[o] + G[k].w - now;
                    dep[t] = dep[o] + 1;
                }
            }
        }
        int dqh = 1, dqt = 0, now = 0;
        drep(i, tai, 1) {
            int o = que[i];
            while(dqh <= dqt && dq[dqh] + dep[o] < D) dqh++;
            while(now + dep[o] < D && now <= mx_dep) now++;
            while(now + dep[o] <= U && now <= mx_dep) {
                int x = now++;
                while(dqh <= dqt && mx[dq[dqt]] < mx[x]) dqt--;
                dq[++dqt] = x;
            }
            if(dqh <= dqt && mx[dq[dqh]] + dis[o] >= 0) return true;
        }
        rep(i, mx_dep + 1, dep[que[tai]]) mx[i] = -1.0 / 0.0;
        rep(i, 1, tai) {
            int o = que[i];
            tomax(mx_dep, dep[o]);
            tomax(mx[dep[o]], dis[o]);
        }
    }
    return false;
}
db mx_ans;
void calc(int o) {
    tot = 0;
    erep(k, G, o) {
        Edge e = G[k];
        if(mark[e.to]) continue;
        data[++tot] = (Data) {e.to, dfs_mx(e.to, o), e.w};
    }
    sort(data + 1, data + 1 + tot);
    db L = ans, R = mx_ans, mid;
    while(R - L >= 1e-4) {
        mid = (L + R) / 2;
        if(check(o, mid)) ans = L = mid;
        else R = mid;
    }
}

int cnt_solve;
void solve(int o, int all) {
    int mn = 1e9;
    dfs_anc(o, 0, all, mn, o);
    calc(o); mark[o] = true;
    erep(k, G, o) {
        int v = G[k].to;
        if(mark[v]) continue;
        solve(v, siz[v] > siz[o] ? all - siz[o] : siz[v]);
    }
}

int main() {
    File(rebuild);
    scanf("%d%d%d", &n, &D, &U);
    mx_ans= 0; ans = 1.0 / 0.0;
    rep(i, 2, n) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        G.add(a, (Edge) {b, c});
        G.add(b, (Edge) {a, c});
        tomin<db>(ans, c);
        tomax<db>(mx_ans, c);
    }
    solve(1, n);
    printf("%.3lf\n", ans);
    return 0;
}