bzoj1758(点分治+单调队列+二分)

Posted on   |   In

题解

经典$0/1$分数规划 二分答案$ans$

对于所有的边权减去$ans$

问题转化成 树上是否存在一条路径 $L<=len<=R$ 并且路径和大于等于0

比较直观的做法 用点分+线段树查询 复杂度$O(nlog^2nlogw)$ 然而会T飞

我们考虑 每个深度对应的是一段区间 总体来看是滑动窗口 然后我们维护的是窗口里面的最大值 所以用单调队列来维护滑动过程中的区间最大值

有个优化的地方是 对于子树的枚举顺序 我们应该考虑按照子树深度递增的顺序去枚举子树 这样会保证复杂度是$O(nlognlogw)$ 否则复杂度会退化

嗯…常数很大 能过全看脸 $xjb$被卡常注意加一些比较有用的剪枝吧

复杂度$O(nlognlogw)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,double>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-4;
#define ll long long
using namespace std;
const int inf=1e9;
struct edge{int t;double v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,double vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,L,R;
int sz[MAXN],rt,key,base,maxx[MAXN];
double K;
bool vis[MAXN];
void get_root(int x,int pre){
    sz[x]=1;maxx[x]=0;
    link(x){
    if(vis[j->t]||j->t==pre)continue;
    get_root(j->t,x);
    sz[x]+=sz[j->t];maxx[x]=max(maxx[x],sz[j->t]);
    }
    maxx[x]=max(maxx[x],base-sz[x]);
    if(key>maxx[x])key=maxx[x],rt=x;
}

double G[MAXN],H[MAXN],dis[MAXN];
int dep[MAXN],St[MAXN],tot1;
int Maxx;
void dfs(int x,int pre){
    H[dep[x]]=max(H[dep[x]],dis[x]);St[++tot1]=x;
    Maxx=max(Maxx,dep[x]);
    link(x){
    if(vis[j->t]||j->t==pre)continue;
    dep[j->t]=dep[x]+1;dis[j->t]=dis[x]+j->v-K;
    dfs(j->t,x);
    }
}

int q[MAXN],ql,qr;
bool flag;
int Dep[MAXN];
inline void get_dep(int x,int pre,int y){
    Dep[y]=max(Dep[y],dep[x]); 
    link(x){
        if(vis[j->t]||j->t==pre)continue;
        dep[j->t]=dep[x]+1;
        get_dep(j->t,x,y);
    }
}
typedef struct node{
    int x,k;double y;
    friend bool operator<(node aa,node bb){return aa.k<bb.k;}
}node;
vector<node>vec[MAXN];
void solve1(int x){
    vis[x]=1;
    link(x){
    if(vis[j->t])continue;
    dep[j->t]=1;get_dep(j->t,x,j->t);
    vec[x].pb((node){j->t,Dep[j->t],j->v});
    }
    sort(vec[x].begin(),vec[x].end());
    link(x){
    if(vis[j->t])continue;
    Dep[j->t]=0;
    key=inf;base=sz[j->t];get_root(j->t,0);
    solve1(rt);
    }
}

void solve(int x){
    vis[x]=1;tot1=0;G[0]=0;
    if(flag)return ;
    int MAxx=0;
    for(int w=0;w<vec[x].size();w++){
    int y=vec[x][w].x;
    Maxx=0;dep[y]=1;dis[y]=vec[x][w].y-K;dfs(y,x);
    int l=min(MAxx+1,max(0,L-Maxx));int r=min(MAxx,max(-1,R-Maxx));ql=1;qr=0;double ans=-inf;
    inc(i,l,r){
        while(ql<=qr&&G[i]>G[q[qr]])qr--;
        q[++qr]=i;
    }
    dec(i,Maxx,1){
        int t1=min(MAxx+1,max(0,L-i));int t2=min(MAxx,max(-1,R-i));
        if(t1>l){
        while(ql<=qr&&q[ql]<t1)ql++;
        l=t1;
        }
        if(t2>r){
        inc(j,r+1,t2){
            while(ql<=qr&&G[j]>G[q[qr]])qr--;
            q[++qr]=j;
        }
            r=t2;
        }
        if(ql<=qr)ans=max(ans,H[i]+G[q[ql]]);
    }
        if(ans>=0.000000)flag=1;
        MAxx=max(MAxx,Maxx);
        inc(i,1,Maxx)G[i]=max(G[i],H[i]),H[i]=-inf;
    }
    G[0]=-inf;
    inc(i,1,tot1)G[dep[St[i]]]=-inf;
    link(x){
        if(vis[j->t]||L+1>sz[j->t])continue;
        key=inf;base=sz[j->t];get_root(j->t,0);
        solve(rt);
    }
}

bool check(double x){
    flag=0;K=x;memset(vis,0,sizeof(vis));
    base=n;key=inf;get_root(1,0);
    solve(rt);
    if(flag)return 1;
    return 0;
}

int main(){
    n=read();L=read();R=read();
    int x,y;double z;
    inc(i,2,n)x=read(),y=read(),scanf("%lf",&z),add(x,y,z),add(y,x,z);
    base=n;key=inf;get_root(1,0);solve1(rt);
    inc(i,1,n)G[i]=H[i]=-inf,vis[i]=0;
    double l=1.0;double r=1000000.0;double ans=0;
    int cnt=0;
    while(r-l>eps){
        double mid=(l+r)/2.0;
        if(check(mid))ans=mid,l=mid;
        else r=mid;
    }
    printf("%.3f\n",ans);
    return 0;
}

题目描述

X国遭受了地震的重创, 导致全国的交通近乎瘫痪，重建家园的计划迫在眉睫。X国由N个城市组成, 重建小组提出，仅需建立N-1条道路即可使得任意两个城市互相可达。于是，重建小组很快提出了一个包含N-1条道路的方案，并满足城市之间两两可达，他们还计算评估了每条道路e建设之后可以带来的价值v(e)。

由于重建计划复杂而艰难，经费也有一定限制。因此，政府要求第一期重建工程修建的道路数目为k条，但需满足L ≤ k ≤ U, 即不应少于L条，但不超过U条。同时，为了最大化利用率，要求建设的这些道路恰好组成一条简单路径，即所建设的k条路径可以构成一个排列$e1 = (p1, q1), e2 = (p2, q2), ek = (pk, qk), 对于 1 ≤ i < k, 有(qi = pi+1)$.

重建小组打算修改他们的原有方案以满足要求，即在原有的N-1条道路中寻找一条路径S作为新的方案，使得新方案中的道路平均价值

$AvgValue = \frac{\sum _{e \in S} v(e)}{|S|}​$

最大。这里v(e)表示道路e的价值，|S|表示新方案中道路的条数。请你帮助重建小组寻找一个最优方案。 注: 在本题中L和U的设置将保证有解。

Input

第一行包含一个正整数$N$，表示$X$国的城市个数。

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

Output

仅包含一行，为一个实数$AvgValue$，即最大平均价值。

小数点后保留三位。