bzoj1758 [Wc2010]重建计划

http://www.elijahqi.win/2018/01/20/bzoj1758/
Description

Input
第一行包含一个正整数N，表示X国的城市个数. 第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限 接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号
Output
输出最大平均估值，保留三位小数
Sample Input
4

2 3

1 2 1

1 3 2

1 4 3
Sample Output
2.500
HINT

N<=100000,1<=L<=U<=N-1,Vi<=1000000 新加数据一组 By leoly,但未重测..2016.9.27
新加一组数据是leoly学长加的orz 虽然网上有人吐槽 但是我仍然觉得挺好的 据说这组数据是扫把形的
题意：求最大的比率即路径权值和/路径条数和的比值最大
首先这是一个分数规划的问题 考虑如何算这个最大值 我们不妨假设现在的最大值是x那么一定满足 ∑i=1nw[i]n>x 我们不妨去二分一下这个x 然后将其变化为 ∑i=1nw[i]−n∗x>0 这个数能否> 0即可 大于0说明我的最大值还可以大 那这题对于每一条路径我都可以通过枚举过根的一条路径去搞出来 所以采用点分的方法 对于这题比较卡常 所以选择在点分里面去二分这个答案 如何验证答案 我每次算出我分治块里的最大值即可 一直取max对于整个块大小< L的点我可以选择忽略 减小常数 如何去求最大能否满足条件 设f[i]表示我当前点分的时候做的这个子树深度为i的dis的最大值 这个dis我已经提前预处理的时候-mid了 g[i]表示我之前所有做过的子树中深度i的最大值是多少 每次我相当于枚举f[i]然后去g中找一个滑动的窗口中的最大值可以单调队列来搞 比较麻烦然后比较下能否> 0如果大于0直接退出即可
注意坑点：退出之后需要将f[],g[]数组重置之后再退出
关于学长这组数据卡的是什么 其实是个小tips 就是我枚举子树的时候需要从深度小的开始向深度大的枚举 这样避免了先做了大的然后每次初始化单调队列和清空f[]数组时所带来的复杂度退化 关于这部分看下代码即可明白
优化：每次二分的L直接设定成上一次的答案即可 因为我至少已经有上一次的答案了 如果不满足那么下界也是上一次的答案

#include<deque>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
#define N 110000
#define pa pair<int,int>
#define eps 1e-4
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0;char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
    return x;
}
struct node{
    int y,z,next;
}data[N<<1];
int ff[N],h[N],root,sum,size[N],dep[N],L,R,num,n;double ans,g[N],f[N],dis[N];bool visit[N];
inline void get_root(int x,int fa){
    ff[x]=0;size[x]=1;
    for (int i=h[x];i;i=data[i].next){
        int y=data[i].y;if (visit[y]||y==fa) continue;
        get_root(y,x);size[x]+=size[y];ff[x]=max(ff[x],size[y]);
    }ff[x]=max(ff[x],sum-size[x]);
    if (ff[root]>ff[x]) root=x;
}
struct node1{
    int y,size,z;
}qq[N];int max1=0;
inline void dfs1(int x,int fa,double mid){
    f[dep[x]]=max(f[dep[x]],dis[x]);max1=max(max1,dep[x]);
    for (int i=h[x];i;i=data[i].next){
        int y=data[i].y,z=data[i].z;if (y==fa||visit[y]) continue;
        dep[y]=dep[x]+1;dis[y]=dis[x]+z-mid;dfs1(y,x,mid); 
    }
}
inline bool check(int x,double mid){
    int max_deep=0;dep[x]=0;dis[x]=0;bool flag=0;
    for (int i=1;i<=num;++i){
        int y=qq[i].y,z=qq[i].z;max1=0;deque<int>q;f[0]=0;
        dep[y]=dep[x]+1;dis[y]=dis[x]+z-mid;dfs1(y,x,mid);max_deep=max(max_deep,max1);
        for (int j=max_deep;j>=L;--j) {
            while(!q.empty()&&g[j]>g[q.back()]) q.pop_back();q.push_back(j);
        }
        for (int j=0;j<=max1;++j){
            while(!q.empty()&&j+q.front()>R) q.pop_front();
            if (!q.empty()) if (f[j]+g[q.front()]-eps>0) {flag=1;break;}
            while(!q.empty()&&L-j-1>=0&&g[L-j-1]>g[q.back()]) q.pop_back();q.push_back(L-j-1);
        }
        for (int j=0;j<=max1;++j) g[j]=max(g[j],f[j]),f[j]=-inf;
        if (flag) break;
    }
    for (int i=0;i<=max_deep;++i) g[i]=-inf;if(flag) return 1;else return 0;
}
inline bool cmp(node1 a,node1 b){return a.size<b.size;}
inline void solve(int x){
    if (sum<L) return;visit[x]=1;num=0;dep[x]=0;
    for (int i=h[x];i;i=data[i].next) {
        int y=data[i].y;if (visit[y]) continue;
        if(size[y]>size[x]) size[y]=sum-size[x];
        qq[++num].size=size[y];qq[num].y=y;qq[num].z=data[i].z;
    }
    sort(qq+1,qq+num+1,cmp);double l=ans,r=1e6;
    while(r-l>eps){
        double mid=(l+r)/2;
        if (check(x,mid)) l=mid;else r=mid;
    }ans=max(ans,l);
    for (int i=h[x];i;i=data[i].next){
        int y=data[i].y;if (visit[y]) continue;
        root=0;sum=size[y];get_root(y,x);solve(root);
    }
}
int main(){
    freopen("bzoj1758.in","r",stdin);
    n=read();L=read();R=read();
    for (int i=0;i<=n;++i) f[i]=g[i]=-inf;
    for (int i=1;i<n;++i){
        int x=read(),y=read(),z=read();
        data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num;
        data[++num].y=x;data[num].z=z;data[num].next=h[y];h[y]=num;
    }sum=n;root=0;ff[0]=inf;get_root(1,0);solve(root);
    printf("%.3f",ans);
    return 0;
}