[bzoj 1758] [Wc2010]重建计划

本文主要是介绍[bzoj 1758] [Wc2010]重建计划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如果莫名地TLE了可以看一看本文. 数据经过加强后, 以前许多AC代码会超时.
新站没被百度收录, 所以在这里复制一份, 希望能帮到您.
https://chrt.github.io/2017/04/09/bzoj1758-rebuild/

一棵n个结点, 边带权的无根树, 求包含[L,U]条边的简单路径的最大平均权值 (权值和/边数), 保留3位小数. (n≤10^5, 1≤L≤U≤n-1, 边权≤10^6)

虽然AC花费了比想象中更多的功夫, 但我认为数据加强后这是一道不错的题.

这是一个0-1分数规划, 考虑二分一下. 问题简化为, 判断是否存在一条简单路径, 使得

(v (e 1) - m) + (v (e 2) - m) + \dots + (v (e k) - m) \geq 0 (k \in [L, U])

$(v(e_1)-m) + (v(e_2)-m) + \cdots + (v(e_k)-m) \ge 0\ (k\in [L, U])$
其中

m $m$ 是二分的答案.

路径相关问题点分治是个不错的选择. 遍历重心的每一棵子树, 设当前结点 $v$ 的深度为 $d(v)$ , 对边权重新赋值后到重心的距离为 $l(v)$ , 需要判断是否存在另一棵子树中的某点 $u$ , 使得

L - d (v) \leq d (u) \leq U - d (v) l (u) \geq - l (v)

$L-d(v) \le d(u) \le U - d(v)\\ l(u) \ge -l(v)$
对于所有深度在

[L−d(v),U−d(v)] $[L-d(v), U-d(v)]$ 的点, 只用考虑距离的数值最大的那个.

这是RMQ问题, 线段树? 两个log好像不太可行……但还是尝试了一下. 本机开O2 3~4s出解, 但是交上去TLE (也许是因为后面将要说的其他原因). 事实上我写了两遍……手敲编译指令, 打错了, 把源代码覆盖了……神奇的是, 之前不开O2无法出解, 重写之后快了不少 (极限数据11s左右).

二分的那个log大概搞不掉了, 大概要换掉线段树. 发现查询的区间有一个特点 - 长度基本是 $U-L$ . 能不能借此优化到均摊 $O(1)$ 呢?

看了题解, 才发觉这就是滑动窗口问题, 单调队列即可搞定. 分别维护之前所有子树和当前子树的深度-长度数组, 做完滑动窗口后合并两个数组即可.

仍然TLE. 以为是常数问题, 参照题解, 做了一些诸如把二分套到点分治里面的优化, 但是无济于事. 卡了一天……大概新加的那组数据有玄机? 复制了神犇以前的AC代码, 结果也TLE了.

想到有个Discuss页面, 看到有人跟我有相同的疑惑. 谜底揭晓: 单调队列做滑动窗口的线性复杂度, 自变量是待查询的数组大小. 点分治保证递归的深度为 $O(\lg n)$ , 但不保证分出来的子树的大小, 深度相近. 所以可以设计这样的数据: 第一棵子树的大小和深度 (从1开始标号) 为n/2, 其余(n/2-1)棵子树大小和深度为1; 每次点分治的时间复杂度退化为 $O(n^2\lg n)$ . 将子树按深度从小到大排序再做滑动窗口即可解决这个问题.

正确地实现, 时间复杂度为 $O(\lg U n\lg n)$ .

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##_end = (b); i < i##_end; ++i)
#define per(i, a, b) for (int i = (a), i##_end = (b); i >= i##_end; --i)using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1e5;
const double inf = 1e16;
struct Edge {int v, w, nxt;
} E[N*2];
int adj[N + 1];bool g[N + 1];
ii subtree[N];
int depth[N], top, sz[N + 1];
double a[N], b[N];
int tot_a, tot_b;
int L, U;int get_centroid(int u, int p, int n);
void counting_sort(int k[], ii v[], int m, int n);void cal_b(int u, int p, double m, int dep, double len)
{if (dep > U) return;if (tot_b < dep+1) {b[dep] = len;tot_b = dep+1;} elseb[dep] = max(b[dep], len);for (int i = adj[u]; i; i = E[i].nxt) {int v = E[i].v;if (g[v] || v == p) continue;cal_b(v, u, m, dep + 1, len + E[i].w - m);}
}void cal_a()
{rep (i, 1, tot_a)a[i] = max(a[i], b[i]);rep (i, tot_a, tot_b)a[i] = b[i];tot_a = tot_b;
}bool check()
{static int Q[N];int front = 0, rear = 0, j = 0;per (i, tot_b-1, 0) { // [L-i, U-i]while (j < tot_a && j <= U-i) {while (rear > front && a[Q[rear-1]] <= a[j]) --rear;Q[rear++] = j++;}while (front < rear && Q[front] < L-i) ++front;if (front < rear && a[Q[front]] + b[i] >= 0)return true;}return false;
}bool judge(int x, double m)
{tot_a = 1;rep (i, 0, top) {int y = subtree[i].first;tot_b = 1;cal_b(y, x, m, 1, subtree[i].second - m);if (check()) return true;cal_a();}return false;
}int cal_depth(int u, int p)
{int d = -1;for (int i = adj[u]; i; i = E[i].nxt) {int v = E[i].v;if (!g[v] && v != p)d = max(d, cal_depth(v, u));}return d+1;
}void solve(int u, int n, double& l, double _r)
{if (n-1 < L) return;int x = get_centroid(u, 0, n), maxd = 0;g[x] = true;top = 0;for (int i = adj[x]; i; i = E[i].nxt) {int v = E[i].v;if (!g[v]) {subtree[top] = ii(v, E[i].w);maxd = max(maxd, depth[top++] = min(U, cal_depth(v, u)+1));}}counting_sort(depth, subtree, maxd + 1, top);double r = _r;while (r-l >= 1e-4) {double m = (l+r)/2;if (judge(x, m)) l = m;else r = m;}for (int i = adj[x]; i; i = E[i].nxt) {int y = E[i].v;if (!g[y]) solve(y, sz[y]>sz[x] ? n-sz[x] : sz[y], l, _r);}
}inline void add_edge(int u, int v, int w)
{static int ptr = 1;E[ptr] = (Edge){v, w, adj[u]};adj[u] = ptr++;
}int main()
{int n;double l = inf, r = 0;scanf("%d%d%d", &n, &L, &U);rep (i, 0, n-1) {int u, v, w;scanf("%d%d%d", &u, &v, &w);add_edge(u, v, w);add_edge(v, u, w);l = min(l, (double)w);r = max(r, (double)w);}solve(1, n, l, r);printf("%.3f\n", l);return 0;
}int get_centroid(int u, int p, int n)
{int mx = 0, x = 0;sz[u] = 1;for (int i = adj[u]; i; i = E[i].nxt) {int v = E[i].v, ret;if (g[v] || v == p) continue;if ((ret = get_centroid(v, u, n))) x = ret;sz[u] += sz[v];mx = max(mx, sz[v]);}return x ? x : (max(mx, n-sz[u]) <= n/2 ? u : 0);
}void counting_sort(int k[], ii v[], int m, int n)
{static int a[N];static ii b[N];fill_n(a, m, 0);rep (i, 0, n) ++a[k[i]];rep (i, 1, m) a[i] += a[i-1];per (i, n-1, 0) b[--a[k[i]]] = v[i];copy(b, b+n, v);
}