BZOJ1758 [WC2010]重建计划（二分答案，长链剖分）

题目链接

洛谷

题意简述

给你一棵带边权的树，求所有长度在 $[L,U]$ 这个范围内的路径里平均权值（总权值除以边数）的最大值。

$2\le n\le 10^5$，保证至少有一条满足要求的路径。

简要做法

#define 父亲 单亲（如果有谴责“父亲节点”人士的话）

首先可以二分答案，就可以把每条边的边权都减去二分的答案，然后转化为判断有没有权值和为正的符合长度要求的路径。

然后有点分治和长链剖分两种做法，本题解介绍长链剖分的做法。

由于合并时要区间查询最大值，可以用线段树来维护。

具体来说，我们可以像重链剖分一样计算 dfs 序时优先 dfs 重（长）儿子，这样的话长链的 dfs 序就是连续的一段。当我们处理到子树 $u$ 时，$dfn_u+k$ 这个位置上的值表示自 $u$ 起向下长度为 $k$ 的路径的最大权值。可以发现不同长链之间不会互相影响，而重儿子的信息只要一个区间加就可以继承给父亲。所以，每次先 dfs 重儿子把信息继承上来，并检查有没有权值和为正的符合长度要求的路径，然后 dfs 轻儿子并枚举深度，在线段树中查询对应的一段长度合法的区间的最大值来检查有没有权值和为正的符合长度要求的路径，并将轻儿子信息也合并上来。

参考代码

代码用了 CF 模板，还请谅解..（只不过这种题就算按正常码风写估计也很难看懂吧..不如自己思考细节如何实现）

#ifndef OUUAN
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#endif
#include<bits/stdc++.h>

#define int LoveLive
//#define FAST_IOSTREAM 1

#define For(i,l,r)for(int i=(l),i##end=(r);i<=i##end;++i)
#define FOR(i,r,l)for(int i=(r),i##end=(l);i>=i##end;--i)
#define SON(i,u)for(int i=head[u];i;i=nxt[i])
#define ms(a,x)memset(a,x,sizeof(a))
#define fi first
#define se second
#define pq priority_queue
#define pb emplace_back
#define isinf(x)(x>=INF?-1:x)
#define DEBUG(x)cerr<<(#x)<<":"<<x<<endl
using namespace std;typedef long long LoveLive;typedef pair<int,int>pii;typedef vector<int>vi;
#ifdef int
const int INF=0x3f3f3f3f3f3f3f3fll;
#else
const int INF=0x3f3f3f3f;
#endif
const double eps=1e-9;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());int randint
(int l,int r){return(int)rng()%(r-l+1)+l;}
#ifdef FAST_IOSTREAM
#define br cout<<'\n'
#define sp cout<<' '
long long read(){long long x;cin>>x;return x;}template<typename T>void read(T&x){cin>>x;}template<typename
T>void write(const T&x){cout<<x;}
#else
#define br putchar('\n')
#define sp putchar(' ')
template<typename T>typename enable_if<!is_integral<T>::value,void>::type read(T&x){cin>>x;}long long
read(){char c;long long out=0,f=1;for(c=getchar();!isdigit(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c
=getchar();}for(;isdigit(c);c=getchar())out=(out<<3)+(out<<1)+c-'0';return out*f;}template<typename T
>typename enable_if<is_integral<T>::value,T>::type read(T&x){char c;T f=1;x=0;for(c=getchar();!isdigit
(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c=getchar();}for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-'0';
return x*=f;}char read(char&x){for(x=getchar();isspace(x);x=getchar());return x;}double read(double
&x){scanf("%lf",&x);return x;}void read(char*x){scanf("%s",x);}template<typename T>typename enable_if
<!is_integral<T>::value,void>::type write(const T&x){cout<<x;}template<typename T>typename enable_if<
is_integral<T>::value,void>::type write(const T&x){if(x<0){putchar('-');write(-x);return;}if(x>9)write
(x/10);putchar(x%10+'0');}void write(const char&x){putchar(x);}void write(const double&x){printf("%.10lf"
,x);}void write(const char*x){printf("%s",x);}
#endif
template<typename T,typename...Args>void read(T&x,Args&...args){read(x);read(args...);}template<typename
...Args>void read(char*x,Args&...args){read(x);read(args...);}template<typename OutputIt,typename=typename
enable_if<is_same<output_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value ||(
is_base_of<forward_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value&&!is_const
<OutputIt>::value)>::type>void read(OutputIt __first,OutputIt __last){for(;__first!=__last;++__first)
read(*__first);}template<typename InputIt,typename=typename enable_if<is_base_of<input_iterator_tag,typename
iterator_traits<InputIt>::iterator_category>::value>::type>void wts(InputIt __first,InputIt __last){
for(;__first!=__last;++__first){write(*__first);sp;}}template<typename InputIt,typename=typename enable_if
<is_base_of<input_iterator_tag,typename iterator_traits<InputIt>::iterator_category>::value>::type>void
wtb(InputIt __first,InputIt __last){for(;__first!=__last;++__first){write(*__first);br;}}void wts(const
char*x){write(x);sp;}void wtb(const char*x){write(x);br;}void wte(const char*x){write(x);exit(0);}template
<typename T>void wts(const T&x){write(x);sp;}template<typename T>void wtb(const T&x){write(x);br;}template
<typename T>void wte(const T&x){write(x);exit(0);}template<typename...Args>void wts(const char*x,Args
...args){wts(x);wts(args...);}template<typename...Args>void wtb(const char*x,Args...args){wts(x);wtb(
args...);}template<typename...Args>void wte(const char*x,Args...args){wts(x);wte(args...);}template<typename
T,typename...Args>void wts(const T&x,Args...args){wts(x);wts(args...);}template<typename T,typename...
Args>void wtb(const T&x,Args...args){wts(x);wtb(args...);}template<typename T,typename...Args>void wte
(const T&x,Args...args){wts(x);wte(args...);}template<typename T>inline bool up(T&x,const T&y){return
x<y?x=y,1:0;}template<typename T>inline bool dn(T&x,const T&y){return y<x?x=y,1:0;}

const int N = 100010;

struct SegmentTree
{
#define ls (cur << 1)
#define rs (cur << 1 | 1)
#define mid ((l + r) >> 1)

    double mx[N << 2], tag[N << 2];

    void reset()
    {
        ms(mx, 0);
        ms(tag, 0);
    }

    void add(int x, double y)
    {
        mx[x] += y;
        tag[x] += y;
    }

    void pushdown(int cur)
    {
        if (fabs(tag[cur]) < eps) return;
        add(ls, tag[cur]);
        add(rs, tag[cur]);
        tag[cur] = 0;
    }

    void modify(int cur, int l, int r, int p, double x)
    {
        up(mx[cur], x);
        if (l == r - 1) return;
        pushdown(cur);
        if (p < mid) modify(ls, l, mid, p, x);
        else modify(rs, mid, r, p, x);
    }

    void madd(int cur, int l, int r, int L, int R, double x)
    {
        if (l >= R || r <= L) return;
        if (L <= l && r <= R) add(cur, x);
        else
        {
            pushdown(cur);
            madd(ls, l, mid, L, R, x);
            madd(rs, mid, r, L, R, x);
            mx[cur] = max(mx[ls], mx[rs]);
        }
    }

    double query(int cur, int l, int r, int L, int R)
    {
        if (l >= R || r <= L) return -INF;
        if (L <= l && r <= R) return mx[cur];
        pushdown(cur);
        return max(query(ls, l, mid, L, R), query(rs, mid, r, L, R));
    }

    double query(int cur, int l, int r, int p)
    {
        if (l == r - 1) return mx[cur];
        pushdown(cur);
        if (p < mid) return query(ls, l, mid, p);
        return query(rs, mid, r, p);
    }

#undef ls
#undef rs
#undef mid
} t;

int head[N], nxt[N << 1], to[N << 1], edge[N << 1], cnt;

void add(int u, int v, int w)
{
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    edge[cnt] = w;
}

int n, mnlen, mxlen, dep[N], son[N], f[N], dfn[N], dfntot;

void dfs1(int u, int fa)
{
    dep[u] = 1;
    SON(i, u)
    {
        int v = to[i];
        if (v == fa) continue;
        f[v] = edge[i];
        dfs1(v, u);
        if(up(dep[u], dep[v] + 1)) son[u] = v;
    }
}

void dfs2(int u, int fa)
{
    dfn[u] = ++dfntot;
    if (son[u]) dfs2(son[u], u);
    SON(i, u)
    {
        int v = to[i];
        if (v != fa && v != son[u]) dfs2(v, u);
    }
}

bool flag;

void dfs(int u, int fa, double x)
{
    if (flag || !son[u]) return;
    dfs(son[u], u, x);
    t.madd(1, 1, n + 1, dfn[son[u]], dfn[son[u]] + dep[son[u]], f[son[u]] - x);
    if (dep[u] - 1 >= mnlen && t.query(1, 1, n + 1, dfn[u] + mnlen, min(dfn[u] + mxlen + 1, dfn[u] + dep[u])) > 0)
    {
        flag = true;
        return;
    }
    SON(i, u)
    {
        int v = to[i];
        if (v != fa && v != son[u])
        {
            dfs(v, u, x);
            t.madd(1, 1, n + 1, dfn[v], dfn[v] + dep[v], f[v] - x);
            For (j, max(0ll, mnlen - dep[u]), min(mxlen - 1, dep[v] - 1))
            {
                if (t.query(1, 1, n + 1, dfn[v] + j) +
                    t.query(1, 1, n + 1, max(0ll, mnlen - j - 1) + dfn[u], min(dep[u], mxlen - j) + dfn[u]) > 0)
                {
                    flag = true;
                    return;
                }
            }
            For (j, 0, dep[v] - 1) t.modify(1, 1, n + 1, dfn[u] + j + 1, t.query(1, 1, n + 1, dfn[v] + j));
        }
    }
}

bool check(double x)
{
    flag = false;

    t.reset();

    dfs(1, 0, x);

    return flag;
}

signed main()
{
#ifdef FAST_IOSTREAM
    cin.sync_with_stdio(false);
    cin.tie(0);
#endif

    read(n, mnlen, mxlen);

    For (i, 2, n)
    {
        int u, v, w;
        read(u, v, w);
        add(u, v, w);
        add(v, u, w);
    }

    dfs1(1, 0);
    dfs2(1, 0);

    double l = 0, r = 1e6;

    For (i, 1, 40)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.3lf", r);

    return 0;
}