bzoj 1758 重建计划
题意：
给定一棵有边权的树和两个数 (L, R (Lleq R))，求一条简单路径，使得这条路径经过的边数在 (L, R) 之间且路径经过的边的边权的平均值最大
背景：
NewTrain里面的题
坑了很长时间
题解：
显然是分数规划
二分答案，然后变成判断是否有路径的边权和大于等于 (0)
考虑点分治，每一层保留下来每个深度对应的最大边权和，然后因为对于一个子树而言，随着深度增加，合法区间是向左移动的，可以用单调队列维护
复杂度？
对于当前的重心，处理某一棵子树的代价为 (max(dep, prev\_dep))，其中 (dep) 表示当前子树的最大深度，(prev\_dep) 表示之前处理的子树的最大深度
为了保证复杂度，我们将子树按照深度排序，可以使得 (dep geq prev\_dep) 对于任何子树成立，那么处理一层的代价变为 (sum dep leq size)
我们发现，不管当前二分的答案是多少，重心的顺序相同，并且对于固定的重心而言，其子树的深度顺序相同，所以都可以预处理，或者直接在点分治内部二分，可以降低常数
（到底是在里面二分快还是在外面二分快啊？好像网上的代码都是在里面二分的，但是栋栋说在外面二分快。。。)
代码：
// Copyright lzt
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<long long, long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i, j, k) for (register int i = (int)(j); i <= (int)(k); i++)
#define rrep(i, j, k) for (register int i = (int)(j); i >= (int)(k); i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = 10 * x + ch - '0';
ch = getchar();
}
return x * f;
}
const int maxn = 100100;
double MX;
int n, L, R, tot, root, rf, mxdep, nwdep;
int head[maxn], to[maxn << 1], nxt[maxn << 1], len[maxn << 1];
int sz[maxn];
bool vis[maxn];
double res, xx, f[maxn], g[maxn];
vector<pii> vec;
inline void addedge(int x, int y, int l) {
to[++tot] = y; nxt[tot] = head[x]; head[x] = tot; len[tot] = l;
to[++tot] = x; nxt[tot] = head[y]; head[y] = tot; len[tot] = l;
}
inline void dfs1(int u, int pa) {
sz[u] = 1;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v == pa || vis[v]) continue;
dfs1(v, u); sz[u] += sz[v];
}
}
inline int getroot(int u, int pa, int S) {
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v == pa || vis[v]) continue;
if (sz[v] * 2 > S) return getroot(v, u, S);
}
rf = pa;
return u;
}
inline bool cmp (pii x, pii y) {
return sz[x.fi] < sz[y.fi];
}
inline void dfs2(int u, int pa, double l, int d) {
if (d > R) return;
g[d] = max(g[d], l); nwdep = max(nwdep, d);
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (vis[v] || v == pa) continue;
dfs2(v, u, l + len[i] - xx, d + 1);
}
}
int q[maxn];
int h, t;
inline bool ok(int u) {
bool flag = 0;
mxdep = 0;
rep(i, 0, vec.size() - 1) {
nwdep = 0;
dfs2(vec[i].fi, u, vec[i].se - xx, 1);
h = 1, t = 0;
rrep(j, min(R, mxdep), L) {
if (j > mxdep) continue;
double nw = f[j];
while (t >= h && nw >= f[q[t]]) t--;
q[++t] = j;
}
if (t >= h && f[q[h]] >= 0) {
flag = 1;
} else {
rep(j, 1, nwdep) {
double nw = f[L - j];
while (nw >= f[q[t]] && t >= h) t--;
q[++t] = L - j;
while (q[h] + j > R) h++;
if (q[h] <= mxdep && q[h] + j >= L && g[j] + f[q[h]] >= 0) {
flag = 1;
break;
}
}
}
mxdep = max(mxdep, nwdep);
rep(j, 1, nwdep) f[j] = max(f[j], g[j]), g[j] = -1e9;
if (flag) break;
}
rep(j, 1, mxdep) f[j] = -1e9;
return flag;
}
void solve(int u, int pa) {
dfs1(u, pa);
root = getroot(u, pa, sz[u]);
sz[rf] = sz[u] - sz[root];
vec.clear();
for (int i = head[root]; i; i = nxt[i]) {
int v = to[i];
if (vis[v]) continue;
vec.pb(mp(v, len[i]));
}
sort(vec.begin(), vec.end(), cmp);
double le = res, ri = MX;
while (ri - le > 1e-4) {
xx = (le + ri) * 0.5;
if (ok(root)) le = xx;
else ri = xx;
}
res = le;
vis[root] = 1;
for (int i = head[root]; i; i = nxt[i]) {
if (vis[to[i]] || sz[to[i]] <= L) continue;
solve(to[i], root);
}
}
void work() {
n = read(); L = read(), R = read();
rep(i, 1, n - 1) {
int x = read(), y = read(), l = read();
addedge(x, y, l); MX = max(MX, l * 1.0);
}
rep(i, 1, n) f[i] = g[i] = -1e9;
solve(1, 0);
printf("%.3lf
", res);
}
int main() {
#ifdef LZT
freopen("in", "r", stdin);
#endif
work();
#ifdef LZT
Debug("My Time: %.3lfms
", (double)clock() / CLOCKS_PER_SEC);
#endif
}
Review
思维难度低，代码难度高
（或者说是我不太会写代码。。。）