传送门 一道树链剖分边权转点权好题 虽然可以用倍增 LCA 做
题意
A 国有 座城市，编号从 到 ，城市之间有 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
思路
很显然要先跑一遍最大生成树，尽量让所有的城市之间以更大限重的道路连接。
然后整个图就变成一棵树了，所以直接用树链剖分处理，找出两点之间路径上最小权值就好了。 注意图有不连通的情况，所以还需要在进行树链剖分时把所有没有访问到的点都 DFS 一遍。
接下来的重头戏就是边权转点权的处理了。
显然一个边只连着一个儿子，但可能多条边连在一个父亲上，所以考虑把边权直接转到儿子的点权值上。 就像下图这样。
然后就这么交上去 WA 成狗
其实我们可以在查询时很轻松地 hack 掉原来的查询方法。 如下图。
如果我们要查询点 路径上的最小权值，我们的输出会是 233，而实际上最小权值应是 256. 显然在 路径上是没有 这条边的，但经过了 这个点，导致 的边权值被计算在内。
如何处理这种情况呢？
只需要在最后，两点 u,v 在同一条重链上时，查询 pos[u] + 1 和 pos[v] 区间的最小值就可以了。
这个方法适用于所有边权转点权的题。
完整代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct Edge {
int next, to, val;
} edge[maxN << 1];
struct Edg {
int from, to, val;
bool operator < (const Edg &rhs) const {
return val > rhs.val;
}
} edg[maxN];
struct node {
int min;
} tree[maxN << 2];
int top[maxN], fa[maxN], dep[maxN], par[maxN];
int pos[maxN], siz[maxN], head[maxN];
int w[maxN], val[maxN];
bool vis[maxN];
int cnt, n, q, m, tim;
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
void unite(int x, int y) {
if (!same(x, y)) par[find(y)] = par[x];
}
void add(int from, int to, int val) {
edge[++cnt] = (Edge) {head[from], to, val};
head[from] = cnt;
}
void kruskal() {
int num = 0;
for (int i = 1; i <= m; i++)
if (!same(edg[i].from, edg[i].to)) {
int u = edg[i].from, v = edg[i].to;
unite(u, v); num++;
add(u, v, edg[i].val);
add(v, u, edg[i].val);
if (num == n - 1) break;
}
}
void dfs1(int u) {
siz[u] = 1, dep[u] = dep[fa[u]] + 1, vis[u] = true;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (v != fa[u]) {
w[v] = edge[i].val; // 边权转点权
fa[v] = u;
dfs1(v);
siz[u] += siz[v];
}
}
}
void dfs2(int u) {
int maxn = 0, nxt = -1;
pos[u] = ++tim;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (v != fa[u] && siz[v] > maxn)
maxn = siz[v], nxt = v;
}
if (nxt == -1) return;
top[nxt] = top[u];
dfs2(nxt);
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (v != fa[u] && v != nxt) {
top[v] = v;
dfs2(v);
}
}
}
struct SegmentTree {
#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid ((l + r) >> 1)
void build(int o, int l, int r) {
if (l == r) {
tree[o].min = val[l];
return;
}
build(ls, l, mid);
build(rs, mid + 1, r);
tree[o].min = min(tree[ls].min, tree[rs].min);
}
int query(int o, int l, int r, int sl, int sr) {
if (sl <= l && r <= sr) return tree[o].min;
int ret = INF;
if (sl <= mid) ret = min(ret, query(ls, l, mid , sl, sr));
if (sr > mid) ret = min(ret, query(rs, mid + 1, r, sl, sr));
return ret;
}
} T;
int query_path(int u, int v) {
int ret = INF;
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) swap(u, v);
ret = min(ret, T.query(1, 1, n, pos[top[v]], pos[v]));
v = fa[top[v]];
}
if (pos[u] > pos[v]) swap(u, v);
ret = min(ret, T.query(1, 1, n, pos[u] + 1, pos[v])); // 在查询时要 pos[u] 要 +1
return ret;
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) par[i] = i;
for (int i = 1, num = 0; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edg[++num] = (Edg) {a, b, c};
}
sort(edg + 1, edg + 1 + m);
kruskal();
for (int i = 1; i <= n; i++)
if (!vis[i]) {
dfs1(i);
top[i] = i;
dfs2(i);
}
for (int i = 1; i <= n; i++) val[pos[i]] = w[i];
T.build(1, 1, n);
scanf("%d", &q);
for (int i = 1, a, b; i <= q; i++) {
scanf("%d%d", &a, &b);
if (!same(a, b)) printf("-1\n");
else printf("%d\n", query_path(a, b));
}
return 0;
}