边分治

以边为分割点，优势是每次只分成两份

思想

在有些树上统计时，发现点分治不能很方便统计（比如与度数有关的问题，或者子树间相互影响过多的问题），此时我们考虑，如果以边为分割，信息似乎变得好统计了起来，且每次只把当前图分成两部分，子树间的影响也好考虑

然后你就兴冲冲把点分治每次取点改错每次取边，还类似找重心一样每次找分成的两个部分边数尽可能平衡的边，高兴的交上去结果被菊花图卡的瓜起

三度化

就是把原树改成二叉树，这里有两种办法一只是直接构造一条虚点链，链上每个点挂一共儿子；第二种是在父亲和儿子之间加足够多的虚点，使其形成一种类似满二叉树的结构；两种方法一个会成链、一个会成满二叉树，显然第一种常数大，但是第二种空间复杂度高（ $O(n \log n)$ ），不论那种都会把点数变成二倍，那么边数自然就要开 $4$ 倍了

然后你就会发现，我们必须巧妙的设计虚点的权，使其不影响答案，这正是边分治的难点

例题

你发现边分治的题几乎都和点分治重了，不和点分治重复的题就是什么边分树 + 虚树的毒瘤或者边分树合并的神仙玩意，所以我们放一道点分治的题来用边分治做：

重建计划

分数规划，二分一下就变成求树上一条权做最大的链，且链长在 $L, U$ 之间，点分治显然（啊啊啊好想写点分治，边分治太难写了）

考虑到这是边分治的例题，我们去将原树三度化，建立的虚点不记录进长度，权值也为 $0$ 就好，然后就像跑点分治一样跑，对于 $L, U$ 的条件，直接 sort 时间会爆炸，点分治的话可以考虑把 walk 从 dfs 换成 bfs 自然就保证有序了，但边分治有 $0$ 权点，我们利用同长度只取最大来解决；总时间 $O(n \log^2 n)$

代码：

由于 luogu 没有边分治题解导致调了半天（似乎还有树剖解法），细节比较多；由于 Dyd 是大常数选手必须开 O2 才能过，感觉可以 FIO + 边分树卡常但人懒了

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using DB = double;
const int N = 1e5 + 100;
const DB eps = 1e-4;
int n, numl, numr;
bool del[N << 2];
DB res, lp[N << 1], rp[N << 1], l = 0, r = 1e6, mid, ans;
std::vector< std::pair<int, int> > G[N << 1];
int h[N << 1], idx = 0, mxs, si[N << 1], rte, cl, cr, hh, tt;
struct Edge{ int ne, ver, w; } e[N << 2];
std::pair<DB, int> q[N << 1];
void add(int x, int y, int z){ e[idx] = {h[x], y, z}, h[x] = idx++; }
void dfs(int x, int fa)
{
    for (int i = h[x]; ~i; i = e[i].ne) if (e[i].ver != fa)
    {
        dfs(e[i].ver, x);
        G[x].pb({e[i].ver, e[i].w});
    }
}
void rebuild()
{
    dfs(1, -1);
    std::memset(h, -1, sizeof h), idx = 0;
    for (int i = 1, lc, rc; i <= n; ++i)
        if (G[i].size() <= 2)
            for (auto t : G[i]) add(i, t.fi, t.se), add(t.fi, i, t.se);
        else
        {
            lc = ++n, rc = ++n;
            add(i, lc, 0), add(lc, i, 0);
            add(i, rc, 0), add(rc, i, 0);
            for (auto t : G[i]) G[lc].pb(t), std::swap(lc, rc);
        }
}
void get_rt(int x, int fa, int tot)
{
    si[x] = 1;
    for (int i = h[x], y, mx; ~i; i = e[i].ne) if (!del[i] && (y = e[i].ver) != fa)
    {
        get_rt(y, x, tot);
        si[x] += si[y], mx = std::max(si[y], tot - si[y]);
        if (mx < mxs) mxs = mx, rte = i;
    }
}
void walk(int x, int fa, int len, DB w, DB *p, int &cp, bool is)
{
    if (is)
    {
        if (cp < len) p[cp = len] = w;
        else p[len] = std::max(w, p[len]);
    }
    si[x] = 1;
    for (int i = h[x], y; ~i; i = e[i].ne) if (!del[i] && (y = e[i].ver) != fa)
    {
        walk(y, x, len + (e[i].w != 0), w + e[i].w - mid * (e[i].w != 0), p, cp, is | (e[i].w != 0));
        si[x] += si[y];
    }
}
void calc(int x, int tot)
{
    mxs = n, rte = -1;
    get_rt(x, -1, tot);
    if (rte ==-1 || del[rte]) return ;
    x = rte; //注意,这里x由点变成边
    del[x] = del[x ^ 1] = true;
    int lc = e[x].ver, rc = e[x ^ 1].ver; //把lc作为基准
    walk(lc, rc, 0, 0, lp, cl = 0, 1);
    walk(rc, lc, e[x].w != 0, e[x].w - mid * (e[x].w != 0), rp, cr = 0, e[x].w != 0);
    hh = 1, tt = 0;
    for (int i = 0, j = cl; i <= cr; ++i)
    {
        while (j >= 0 && i + j >= numl)
        {
            while (hh <= tt && q[tt].fi < lp[j]) --tt;
            q[++tt] = {lp[j], j};
            --j;
        }
        while (hh <= tt && i + q[hh].se > numr) ++hh;
        if (hh <= tt) res = std::max(res, rp[i] + q[hh].fi);
    }
    calc(lc, si[lc]), calc(rc, si[rc]);
}
bool chk()
{
    for (int i = 0; i < idx; ++i) del[i] = false;
    res = -1e9;
    calc(1, n);
    return res >= 0;
}
int main()
{
    std::memset(h, -1, sizeof h), idx = 0;
    scanf("%d %d %d", &n, &numl, &numr);
    for (int i = 1, x, y, z; i < n; ++i) scanf("%d %d %d", &x, &y, &z), add(x, y, z), add(y, x, z);
    rebuild();
    while (r - l > eps)
    {
        mid = (l + r) / 2;
        if (chk()) ans = l = mid;
        else r = mid;
    }
    printf("%.3lf\n", ans);
    return 0;
}