题目地址：洛谷：【P4292】[WC2010]重建计划 – 洛谷、BZOJ：Problem 1758. — [Wc2010]重建计划

题目描述

题意简述

给你一棵树，求长度在[L, U]范围内的树链的边权平均值的最大值。

输入输出格式

输入格式：
第一行包含一个正整数N，表示X国的城市个数。
第二行包含两个正整数L、U，表示政府要求的第一期重建方案中修建道路数的上下限。
接下来的N-1行描述重建小组的原有方案，每行三个正整数ai, bi, vi，分别表示道路(ai, bi)，其价值为vi。其中城市由1…N标号。

输出格式：
仅包含一行，为一个实数AvgValue，即最大平均价值。
小数点后保留三位。

输入输出样例

输入样例#1：

4 
2 3 
1 2 1 
1 3 2 
1 4 3

输出样例#1：

2.500

说明

新方案中选择路径(3, 1), (1, 4)可以得到的平均价值为2.5，为最大平均价值。
对于20%的数据，N ≤ 5 000;
另有30%的数据，N ≤ 100 000, 原有方案恰好为一条路径(链);
对于100%的数据，N ≤ 100 000, 1 ≤ L ≤ U ≤ N-1, vi ≤ 10^6。

题解

整个树找树链可以考虑使用点分治。
对于每个重心，我们考虑二分答案，验证的时候找两条子树到重心的路径拼起来长度在范围内的，或者一条路径长度就在范围内的，在处理边权和的时候在每个边权上减掉答案，则只需要判断边权和是否不小于0即可。
由于对于以前找到过的每一个深度的链，只需要存下边权和最大值，就可以直接拿来判断了。而枚举每个深度去遍历合法区间，会造成复杂度退化为$O(n^2)$。我们考虑单调队列优化这一过程，从浅到深枚举当前遍历子树的每个节点，对应的在以前找到过的深度区间可以确定为[L-d, R-d]，由于遍历的顺序单调，单调队列可以倒着从深到浅维护最大值来判定，遍历节点时使用BFS，这样节点的遍历顺序就是从浅到深单调的了，这样判定的复杂度是$O(n)$的了。
单调队列的复杂度其实应该是$O(之前找到过的最大深度)$的，因此，我们可以对每一棵子树的深度进行排序，从浅的子树开始遍历，可以优化时间，不过我采用了快排，排序复杂度会多一个$\log n$。
另外，本题有一定的卡常数成分，有以下几个卡常的地方可以作为参考：

1. 每次遍历需要初始化最大值数组，可以到用的时候再初始化（参见121~123行）；
2. 对于大小小于L的子树，是找不到符合条件的链的，因此可以不用递归下去处理（参见145行）；
3. 可以使用计数排序代替快排（没写）；
4. 读入优化，fread（我的文件头）；
5. 存树用邻接表而不是vector；
6. 自己实现的max函数代替STL的；
7. 手写BFS的队列；
8. 二分答案的时候，可以将左端点设为已经找到的解，右端点设为最大边权，这样每次二分只会去找比当前解更优的解更新。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline int max(int a, int b) {
    return a > b ? a : b;
}

inline double max(double a, double b) {
    return a > b ? a : b;
}

const int MAXN = 100005;
const double EPS = 1e-4;

int n, L, U;
double ans;

struct Edge {
    int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int w) {
    gra[tot] = Edge {v, w, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, w, head[v]}; head[v] = tot++;
}

bool vis[MAXN];
int siz[MAXN], rt, rtsiz;

inline void findrt(int u, int fa, int tot) {
    siz[u] = 1; int msiz = 0;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] || v == fa) continue;
        findrt(v, u, tot);
        siz[u] += siz[v];
        msiz = max(msiz, siz[v]);
    }
    msiz = max(msiz, tot - siz[u]);
    if(msiz < rtsiz) {
        rt = u; rtsiz = msiz;
    }
}

int fa[MAXN], dep[MAXN], que[MAXN], deq[MAXN];
double dis[MAXN];

int tdep[MAXN], subt[MAXN], subw[MAXN], stot;

inline bool cmp(int a, int b) {
    return tdep[a] < tdep[b];
}

inline int dfs(int u, int fa, int dep) {
    int mxdep = dep;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] || v == fa) continue;
        mxdep = max(mxdep, dfs(v, u, dep + 1));
    }
    return mxdep;
}

double mx[MAXN];

inline bool check(int u, double mid) {
    int mxdep = 0;
    stot = 0;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        subt[++stot] = v;
        subw[v] = gra[i].w;
        tdep[v] = dfs(v, u, 1);
    }
    std::sort(subt + 1, subt + stot + 1, cmp);
    for(register int i = 1; i <= stot; i++) {
        int v = subt[i];
        if(vis[v]) continue;
        int hd = 0, tl = 1; fa[v] = u; dep[v] = 1; dis[v] = subw[v] - mid; que[0] = v;
        while(hd < tl) {
            int uu = que[hd++];
            for(register int j = head[uu]; ~j; j = gra[j].nxt) {
                int vv = gra[j].to;
                if(vis[vv] || vv == fa[uu]) continue;
                fa[vv] = uu;
                dep[vv] = dep[uu] + 1;
                dis[vv] = dis[uu] + gra[j].w - mid;
                que[tl++] = vv;
            }
        }
        int l = 1, r = 0, now = mxdep;
        for(register int j = 0; j < tl; j++) {
            int p = que[j];
            while(dep[p] + now >= L && now >= 0) {
                while(l <= r && mx[deq[r]] < mx[now]) r--;
                deq[++r] = now; now--;
            }
            while(l <= r && dep[p] + deq[l] > U) l++;
            if(l <= r && dis[p] + mx[deq[l]] + EPS >= 0) return true;
        }
        for(register int j = mxdep + 1; j <= dep[que[tl - 1]]; j++) {
            mx[j] = -1e9;
        }
        for(register int j = 0; j < tl; j++) {
            int p = que[j];
            mx[dep[p]] = max(mx[dep[p]], dis[p]);
        }
        mxdep = max(mxdep, dep[que[tl - 1]]);
    }
    return false;
}

int lim;

inline void divide(int u) {
    register double l = ans, r = lim, mid;
    while(r - l > EPS) {
        mid = (l + r) / 2;
        if(check(u, mid)) l = mid; else r = mid;
    }
    ans = l;
    vis[u] = true;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] || siz[v] < L) continue;
        rt = 0; rtsiz = n; findrt(v, u, siz[v]);
        divide(rt);
    }
}

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); L = readint(); U = readint();
    for(register int i = 1, a, b, c; i < n; i++) {
        a = readint(); b = readint(); c = readint();
        lim = max(lim, c);
        addedge(a, b, c);
    }
    rt = 0; rtsiz = n; findrt(1, 0, n);
    divide(rt);
    printf("%.3lf", ans);
    return 0;
}