「BZOJ1758」[WC2010]重建计划

Description

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

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

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

AvgValue=eSv(e)SAvgValue = \frac{\sum _{e \in S} v(e)}{|S|}

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

Input

第一行包含一个正整数NN,表示X国的城市个数。

第二行包含两个正整数LLUU,表示政府要求的第一期重建方案中修建道路数的上下限。

接下来的N1N-1行描述重建小组的原有方案,每行三个正整数aia_i, bib_i, viv_i,分别表示道路(ai,bi)(a_i, b_i),其价值为viv_i。其中城市由1N1\cdots N标号。

Output

输出最大平均估值,保留三位小数

Sample Input

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

Sample Output

1
2.500

HINT

N100000,1LUN1,Vi1000000N\leq100000,1\leq L\leq U \leq N-1,V_i\leq1000000

Solution

最初方法

f[x][i]f[x][i] 表示子树xx内长度为ii的链最大价值
g[x][i]g[x][i] 表示子树内长度为ii最大价值
f[x][i]=max{f[y][i1]+w}f[x][i] = \max\{f[y][i - 1] + w\}
g[x][i]=max{f[x][i1]+g[y][i]+w,g[x][i]+f[y][i1]+w}g[x][i] = \max\{f[x][i - 1] + g[y][i] + w,g[x][i] + f[y][i - 1] + w\}
g[x][i]=max{g[x][i],g[y][i]}g[x][i] = \max\{g[x][i], g[y][i]\}
时间复杂度是O(n3)O(n^3),显然很蠢

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 110000;
int n;
struct Edge {
int u, v, nxt;
ll w, t;
}e[N * 2];
int en ,head[N];
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
e[en].t = z;
}
int len[N], son[N];
void DFS(int x, int F) {
len[x] = 1;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
DFS(y, x);
if(len[y] > len[son[x]]) {
son[x] = y;
len[x] = len[y] + 1;
}
}
}
int L, R;
double f[5100][5100], g[5100][5100];
void dfs(int x, int F) {
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs(y, x);
for(int j = n; ~j; --j) {
for(int k = j-1; ~k; --k) {
g[x][j] = max(g[x][j], f[x][k] + f[y][j - k - 1] + e[i].w);
}
g[x][j] = max(g[x][j], g[y][j]);
if(j)f[x][j] = max(f[x][j], f[y][j - 1] + e[i].w);
}
}
}
int main() {
n = read();
L = read(), R = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read(), z = read();
addedge(x, y, z);
addedge(y, x, z);
}
DFS(1, 0);
dfs(1, 0);
printf("%.3f\n", ans);
return 0;
}

改变状态

看到是要求平均数,就想到01规划,直接上二分。
枚举答案,然后fx,if_{x,i}表示子树内长度为ii的链最大值。
显然枚举到儿子yy的时候可以枚举ii,然后在儿子[Li,Ri][L-i,R-i]的长度里找个最大值暴力合并。看上去还是O(n3logk)O(n^3\log k)的。KK是答案取值范围
但是可以长链剖分优化这个过程。

  1. 在长链上从fy,i1f_{y,i-1}转移到fx,if_{x,i}可以O(1)O(1)用指针实现
  2. 在长链链头合并,fy,i1f_{y,i-1}转移到fx,if_{x,i}总共是O(len[k])O(\sum len[k])lenklen_k是不同长链的长度。

每次合并的时候枚举长度ii然后在yy中长度为[Li,Ri][L-i,R-i]中取最大值,复杂度总共是O(len[k])O(\sum len[k])
每一次直接线段树求[L,R][L,R]里的最大值
所以最后的复杂度是O(nlognlogk)O(n\log n \log k)

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cassert>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 120000;
int n;
struct Edge {
int u, v, nxt;
int w;
}e[N * 2];
int en ,head[N];
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
e[en].w = z;
}
int len[N], son[N];
int ww[N];
void DFS(int x, int F) {
len[x] = 1;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
DFS(y, x);
if(len[y] > len[son[x]]) {
son[x] = y;
len[x] = len[y] + 1;
ww[x] = e[i].w;
}
}
}
int L, R, id[N], num;
double f[N], t[N*4];
#define lch (o<<1)
#define rch (o<<1|1)
void build(int o, int l, int r) {
t[o] = -1e99;
if(l == r) return;
int mid = (l + r) >> 1;
if(l <= mid) build(lch, l, mid);
if(r > mid) build(rch, mid + 1, r);
}
void ins(int o, int l, int r, int x, double v) {
/*if(l == r) {
t[o] = v;
return;
}*/
t[o] = max(t[o], v);
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) ins(lch, l, mid, x, v);
else ins(rch, mid + 1, r, x, v);
//t[o] = max(t[lch], t[rch]);
}
double query(int o, int l, int r, int ql, int qr) {
if(ql <= l && qr >= r) return t[o];
int mid = (l + r) >> 1;
if(qr <= mid) return query(lch, l, mid, ql, qr);
if(ql > mid) return query(rch, mid + 1, r, ql, qr);
return max(query(lch, l, mid, ql, qr), query(rch, mid + 1, r, ql,qr));
}
double res, mid;
void dfs(int x, int F) {
if(!id[x]) id[x] = ++num;
f[id[x]] = 0;
if(son[x]) {
dfs(son[x], x);
f[id[x]] = f[id[son[x]]] + ww[x] - mid; //到底端的长度
}
ins(1, 1, n, id[x], -f[id[x]]);
for(int i = head[x]; i; i =e[i].nxt) {
int y = e[i].v;
if(y == F || y == son[x]) continue;
dfs(y, x);
for(int j = 1; j <= len[y] && j <= R; ++j) if(L - j <= len[x] - 1){
double t = f[id[y]] - f[id[y] + (j - 1)] + e[i].w - mid;
int ls = id[x] + L - j;
int rs = id[x] + R - j;
ls = max(id[x], ls);
ls = min(id[x] + len[x] - 1, ls);
rs = min(id[x] + len[x] - 1, rs);
rs = max(id[x], rs);
t += f[id[x]] + query(1, 1, n, ls, rs);
res = max(res, t);
}
for(int j = 1; j <= len[y]; ++j) { //替换链
double t = f[id[y]] - f[id[y] + (j - 1)] + e[i].w - mid;
if(t > f[id[x]] - f[id[x] + j]) {
f[id[x] + j] = f[id[x]] - t;
ins(1, 1, n, id[x] + j, -f[id[x] + j]);
}
}
}
if(len[x] - 1 >= L) res = max(res, f[id[x]] + query(1, 1, n, id[x] + L, id[x] + min(len[x] - 1, R)));
if(res >= -1e-10) return ;
}
bool check(double mid) {
build(1, 1,n);
res = -1e18;
dfs(1, 0);
return res >= -1e-10;
}
int main() {
n = read();
L = read(), R = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read(), z = read();
addedge(x, y, z);
addedge(y, x, z);
}
DFS(1, 0);
double l = 0, r = 1e9;
while(r - l > 1e-5) {
mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.3f\n", l);
return 0;
}