BZOJ1758 [WC2010]重建计划(二分答案,长链剖分)

题目链接

洛谷

题意简述

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

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

简要做法

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

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

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

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

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

参考代码

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

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
#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;
}