初识最小瓶颈路其实是上海那道著名的铜牌题，其次就是 P1396 营救。
P1967 [NOIP2013 提高组] 货车运输 / 最小瓶颈路
\(\mathcal O(m \log m + (n + q)\log n)\) 最大生成树（森林）两点间最小边权，直接在倍增 lca 向上爬的时候更新答案。
问题反过来，最小生成树上的瓶颈（最大边权）也是一样的，双倍经验捏：LOJ #136. 最小瓶颈路
注意不能使用 dep[u] = dep[p] + 1 而将 \(p = 0\)，换言之不能 dfs(i, 0)，为了避免重复访问，dfs 的时候不记父亲节点。
展开代码
void dfs(int u) {
for (int i = h[u]; i; i = graph[i].t) {
if (int v = graph[i].f; !dep[v]) {
dep[v] = dep[u] + 1, f[v][0] = u, w[v][0] = graph[i].w;
dfs(v);
}
}
}
// ...
for (int i = 1; i <= n; i++) if (!dep[i]) {
dep[i] = 1;
dfs(i);
f[i][0] = i; // 之前因为这里无脑设成 f[u][0] = p 而一直出错
w[i][0] = INT_MAX;
}
哇呜呜，怎么还有加强版，学！
LOJ#137. 最小瓶颈路（加强版）/ Kruskal 重构树
使用 Kruskal 重构树来求解。 感觉已经看过太多太多次克鲁斯卡尔重构树了，但是都没有认真学过。
最小瓶颈路
= 最小生成树两点间简单路径上的最大值
= Kruskal 重构树上两点之间的 \(\mathop{lca}\) 的权值。
建立 Kruskal 重构树就是在做 Kruskal 的过程中，原本要合并 \(u\) 和 \(v\)，现在改为新建一个点 \(t\)，连边 \(u \leftarrow t \rightarrow v\)，\(t\) 的点权设为 \(u, v\) 的边权。
这方法对最大生成树两点间最小边权也适用。
void Kruskal() {
sort(edge + 1, edge + 1 + m, cmp);
for (int i = 1; i <= n; ++i) ff[i] = i;
for (int i = 1; i <= m; ++i) {
int fu = find(edge[i].u), fv = find(edge[i].v);
if (fu != fv) {
val[++cnt] = edge[i].dis;
ff[cnt] = ff[fu] = ff[fv] = cnt;
add(fu, cnt), add(cnt, fu);
add(fv, cnt), add(cnt, fv);
}
}
}
倍增可以得 \(75 \rm pts\)，树剖可以得 \(90 \rm pts\)。
100pts（Tarjan / RMQ 求 lca）
满分得配合 Tarjan / RMQ 求 \(\mathop{lca}\)，这俩都是离线算法，不过看起来貌似 RMQ 更厉害一点。
草，怎么还要复习稀疏表，咋写的来着。
用 \(f_{i, j}\) 表示 \([i, i + 2^j)\) 的答案，只要有 \(x \mathop{op} x = x\) 就可以用。递推就是倍增：
\[f_{i, j} = f_{i, j - 1} \mathop{op} f_{i + 2^{j - 1}, j - 1} \]反正就是 \([i, i + 2^{j - 1}) \cup [i + j^{j - 1}, i + 2 \times 2 ^ {j - 1}) = [i, i + 2^j)\)。
查询的时候就拆成 \([l, l + 2 ^ t) \cup [r - 2^t + 1, r]\)。
结论是：记 \(\text{pos}_u\) 为 \(u\) 在欧拉序中第一次出现的位置，则
\[\text{pos}_{\mathop{lca}(u, v)} = \min\limits_{k = u}^v\{ \text{pos}_k \} \]意为从 \(u\) 走到 \(v\) 经过欧拉序最小的节点就是 \(\mathop{lca}(u, v)\)。
记个板子，明天再背。
void dfs(int now, int fa) {
dpth[now] = dpth[fa] + 1;
sec[++cnt] = now;
pos[now] = cnt;
for (int i = head[now]; i; i = e[i].nxt) {
if (fa != e[i].to) {
dfs(e[i].to, now);
sec[++cnt] = now;
}
}
}
void init() {
dfs(2 * n - 1, 0);
for (int i = 1; i <= 4 * n; i++) {
dp[i][0] = sec[i];
}
for (int j = 1; j <= 19; j++) {
for (int i = 1; i + (1 << j) - 1 <= 4 * n; i++) {
dp[i][j] = dpth[dp[i][j - 1]] < dpth[dp[i + (1 << (j - 1))][j - 1]]
? dp[i][j - 1]
: dp[i + (1 << (j - 1))][j - 1];
}
}
}
int lca(int x, int y) {
int l = pos[x], r = pos[y];
if (l > r) {
swap(l, r);
}
int k = log2Values[r - l + 1];
return dpth[dp[l][k]] < dpth[dp[r - (1 << k) + 1][k]]
? dp[l][k]
: dp[r - (1 << k) + 1][k];
}
现在，终于可以来看看这道题了。
Life is a game
先学了一个单词 threshold(/ˈθreʃˌhoʊld/): 门槛，瓶颈。
题意
\(n\) 个点 \(m\) 条边，点权表示这个点拥有的金币（只能获得一次），边权表示前往联通的点至少需要有 \(w\) 金币。
多组询问：从 \(x\) 点出生，初始拥有 \(k\) 个金币，最多可以得到的金币数为多少？
\(n, m, q \leq 10^5; a_i \leq 10^4; k, w \leq 10 ^ 9\)
实际的边权为 \(w_i - a_u, w_i - a_v\)，随后在 Kruskal 重构树上不断向上爬，直到 \(w_{x, i} \gt k\)，此时 \(a_x + k\) 即为所求。
展开代码
#include <bits/stdc++.h>
using ll = long long;
const int N = 200010, M = N * 2;
int n, m, q;
ll a[N];
int val[N], t = 0, f[N][20];
ll w[N][20];
struct edge {
int f, w, t;
bool operator< (const edge &_) const {
return w < _.w;
}
} mst[N];
int p[N];
int find(int x) {
return p[x] = p[x] == x ? x : find(p[x]);
}
void Kruskal() {
std::sort(mst + 1, mst + m + 1);
for (int i = 1; i <= n * 2; i++)
p[i] = i;
t = n;
for (int i = 1, edgs = 0; i <= m; i++) {
int u = find(mst[i].f);
int v = find(mst[i].t);
int w = mst[i].w;
if (u != v) {
a[++t] = a[u] + a[v];
p[u] = p[v] = f[u][0] = f[v][0] = t;
::w[u][0] = w - a[u];
::w[v][0] = w - a[v];
edgs += 1;
}
if (edgs == n - 1)
break;
}
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++) scanf("%lld", a + i);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
mst[i] = {u, w, v};
}
Kruskal();
a[0] = a[t];
int lg = std::__lg(t) + 1;
for (int j = 1; j <= lg; j++) {
for (int i = 1; i <= t; i++) {
f[i][j] = f[f[i][j - 1]][j - 1];
w[i][j] = std::max(w[i][j - 1], w[f[i][j - 1]][j - 1]);
}
}
while (q --) {
int x, k;
scanf("%d%d", &x, &k);
for (int i = lg; ~i; i--) {
if (w[x][i] <= k)
x = f[x][i];
}
printf("%lld\n", a[x] + k);
}
return 0;
}
总结
今天一直在学习树上问题，希望在天梯赛之前能够磨练自己的数据结构和树论水平，等天梯赛选上西安之后再复习数论。慢慢地要改变之前的学习方式了，得开始背一背板子，定期做做复习工作。
加油喵。
标签：瓶颈,Kruskal,20230410,最小,dfs,int,lca,now From： https://www.cnblogs.com/patricky/p/train-20230410.html