1. 例题引入：BZOJ3551
用一道例题引入：BZOJ3551
- 这道题的离线做法可以是线段树合并，可以参照我之前写过的一篇文章，里面有提到：【学习笔记】线段树的扩展（线段树的合并与分裂、可持久化线段树）
- 强制在线的话，我们似乎没有什么好思路。
- 先不考虑求第 \(k\) 大的权值，我们先考虑快速判断点对 \((u,v)\) 能否通过边权不超过 \(x\) 的边互相到达。
- 从最优化的角度考虑，把问题转化为从点 \(u\) 出发，寻找一条 \((u,v)\) 之间的路径，使得这条路径的边权最大值最小。我们需要判断的是这个最小的最大边权是否不超过 \(x\)。
- 因为无向图形态固定，所以我们要找到一条 \((u,v)\) 之间的路径，使得这条路径的边权最大值最小，实际上就是找到最小生成树中的 \((u,v)\) 之间的路径的最大边权。
- 然而如果只是查询最大边权写个树上倍增就没了。
这里我们需要访问从点 \(u\) 出发，能到达所有点的集合。很明显，这个集合是一个连通块，在 \(Kruskal\) 算法的过程中，这个连通块必然在某一时刻是完整存在于一个集合的（因为边一定从小到大接进来的），我们利用这一点，可以将点按照它们之间能到达的最大边权进行分类，于是就有了 \(Kruskal\) 重构树。
2. Kruskal 重构树的构造过程
- 具体做法：
- 我们把新构建出的图叫做重构树，开始重构树中只有 \(n\) 个孤立的点，我们将它们的点权视作 \(-\infty\)。
- 在 \(Kruskal\) 算法求最小生成树的过程中，遇到一条连接两个不同集合的边，我们在并查集中分别找到两个集合的根 \(u,v\)，新建一个结点 \(w\)，合并两个集合，并且令 \(w\) 为新集合的根。
- 在重构树中将 \(w\) 作为 \(u,v\) 共同的父亲，即在重构树中连边 \(w\to u,w\to v\)。令 \(w\) 的点权为 \((u,v)\) 的边权。
3. Kruskal 重构树的性质
- 根据此构造过程，我们可以得到关于重构树的性质：
- 重构树是一棵二叉树，且满足大根堆的性质。
- 原图中的 \(n\) 个点均为重构树中的叶子结点。
- 对于点对 \((u,v)\)，它们在原图中的所有路径中，最大边权最小的路径的最大边权为，\(u,v\) 在重构树中 \(lca\) 的权值。
- 对于一个叶子结点 \(u\)，它在原图中经过边权不超过 \(x\) 的边，能到达的点集为：找到一个深度最小的 \(u\) 的祖先 \(v\)，使得 \(v\) 的点权不超过 \(x\)，根据 \(Kruskal\) 算法的过程和重构树的性质，可以知道，\(v\) 的子树中的叶子结点集合即为能到达的点集。对于一个叶子结点 \(u\)，它在原图中经过边权不超过 \(x\) 的边，能到达的点集为：找到一个深度最小的 \(u\) 的祖先 \(v\)，使得 \(v\) 的点权不超过 \(x\)，根据 \(Kruskal\) 算法的过程和重构树的性质，可以知道，\(v\) 的子树中的叶子结点集合即为能到达的点集。
4. 回到例题：BZOJ3551
- 那么题目中的询问，我们利用性质4，在重构树中找到深度最小的满足条件的结点 \(u\)。
- 然后求子树的叶子节点中的 \(k\) 大权值，我们可以转化为 \(dfs\) 序的区间内的 \(k\) 大权值，然后就是经典的静态区间 \(k\) 大问题。
- 这个只需要对 \(dfs\) 序的每个前缀 \(1\dots i\) 利用主席树（可持久化线段树）维护出权值线段树的每个值域区间的元素个数，查询时候只需要差分一下，在两棵权值线段树上二分即可。
- 如果不清楚静态区间 \(k\) 大的可以自行百度搜索一下主席树。
- 总结一下，对于图的形态不变，并且需要限制通过边权小于或大于某个值的边，关于点的连通性的在线查询问题，可以考虑 \(Kruskal\) 重构树。
5. 相关题目
附：例题 BZOJ3551 代码
#include <bits/stdc++.h>
inline char nextChar()
{
static const int buffer_size = 2333333;
static char buffer[buffer_size];
static const char *tail = buffer + buffer_size;
static char *head = buffer + buffer_size;
if (head == tail)
{
fread(buffer, 1, buffer_size, stdin);
head = buffer;
}
return *head++;
}
template <class T>
inline void read(T &x)
{
static char ch;
while (!isdigit(ch = nextChar()));
x = ch - '0';
while (isdigit(ch = nextChar()))
x = x * 10 + ch - '0';
}
inline void putChar(char ch)
{
static const int buffer_size = 2333333;
static char buffer[buffer_size];
static const char *tail = buffer + buffer_size;
static char *head = buffer;
if (ch == '\0')
fwrite(buffer, 1, head - buffer, stdout);
*head++ = ch;
if (head == tail)
fwrite(buffer, 1, buffer_size, stdout), head = buffer;
}
template <class T>
inline void putint(T x)
{
static char buf[22];
static char *tail = buf;
if (!x) return (void)(putChar('0'));
if (x < 0) x = ~x + 1, putChar('-');
for (; x; x /= 10) *++tail = x % 10 + '0';
for (; tail != buf; --tail) putChar(*tail);
}
const int MaxNV = 2e5 + 5;
const int MaxNE = 5e5 + 5;
const int MaxLog = 20;
const int MaxS = MaxNV * 30;
struct edge
{
int u, v, w;
inline bool operator < (const edge &rhs) const
{
return w < rhs.w;
}
inline void scan()
{
read(u), read(v), read(w);
}
}e[MaxNE];
struct halfEdge
{
int v;
halfEdge *next;
}adj_pool[MaxNE], *adj[MaxNV], *adj_tail = adj_pool;
int n, m, Q, dfs_clock, last_ans, tot;
int rt, cnt, idx[MaxNV], seg[MaxNV];
int h[MaxNV], lef[MaxNV], rit[MaxNV];
int dep[MaxNV], anc[MaxNV][MaxLog + 1];
int ufs_fa[MaxNV], val[MaxNV];
int real_num, real[MaxNV];
int lc[MaxS], rc[MaxS], sze[MaxS];
inline void addEdge(int u, int v)
{
adj_tail->v = v;
adj_tail->next = adj[u];
adj[u] = adj_tail++;
}
inline int ufs_find(int x)
{
return x == ufs_fa[x] ? x : ufs_fa[x] = ufs_find(ufs_fa[x]);
}
inline int jump(int u, int k)
{
for (int i = MaxLog; i >= 0; --i)
if (anc[u][i] && val[anc[u][i]] <= k)
u = anc[u][i];
return u;
}
inline void dfs_init(int u)
{
if (u <= n) idx[lef[u] = ++dfs_clock] = u;
for (int i = 0; anc[u][i]; ++i)
anc[u][i + 1] = anc[anc[u][i]][i];
for (halfEdge *e = adj[u]; e; e = e->next)
{
anc[e->v][0] = u;
dfs_init(e->v);
if (!lef[u]) lef[u] = lef[e->v];
}
rit[u] = dfs_clock;
}
inline void insert(int lst, int &x, int l, int r, int pos)
{
x = ++tot;
lc[x] = lc[lst], rc[x] = rc[lst], sze[x] = sze[lst] + 1;
if (l == r) return;
int mid = l + r >> 1;
pos <= mid ? insert(lc[lst], lc[x], l, mid, pos) : insert(rc[lst], rc[x], mid + 1, r, pos);
}
inline int query(int x, int y, int l, int r, int k)
{
if (l == r) return l;
int mid = l + r >> 1, rsze = sze[rc[x]] - sze[rc[y]];
return k <= rsze ? query(rc[x], rc[y], mid + 1, r, k) : query(lc[x], lc[y], l, mid, k - rsze);
}
int main()
{
read(n), read(m), read(Q);
for (int i = 1; i <= n; ++i)
{
read(h[i]);
real[++real_num] = h[i];
}
std::sort(real + 1, real + real_num + 1);
real_num = std::unique(real + 1, real + real_num + 1) - real - 1;
for (int i = 1; i <= n; ++i)
{
ufs_fa[i] = i;
h[i] = std::lower_bound(real + 1, real + real_num + 1, h[i]) - real;
}
cnt = n;
for (int i = 1; i <= m; ++i)
e[i].scan();
std::sort(e + 1, e + m + 1);
for (int i = 1; i <= m; ++i)
{
int u = ufs_find(e[i].u), v = ufs_find(e[i].v);
if (u != v)
{
val[++cnt] = e[i].w;
ufs_fa[u] = ufs_fa[v] = ufs_fa[cnt] = cnt;
addEdge(cnt, u), addEdge(cnt, v);
}
}
rt = ufs_find(1);
dfs_init(rt);
for (int i = 1; i <= n; ++i)
insert(seg[i - 1], seg[i], 1, real_num, h[idx[i]]);
while (Q--)
{
int u, x, k;
read(u), read(x), read(k);
u = jump(u, x);
last_ans = k <= rit[u] - lef[u] + 1 ? real[query(seg[rit[u]], seg[lef[u] - 1], 1, real_num, k)] : 0;
putint(last_ans ? last_ans : -1);
putChar('\n');
}
putChar('\0');
return 0;
}