树链剖分边权转点权 — 题解 for 货车运输

传送门 一道树链剖分边权转点权好题 虽然可以用倍增 LCA 做

题意

A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

思路

很显然要先跑一遍最大生成树，尽量让所有的城市之间以更大限重的道路连接。

然后整个图就变成一棵树了，所以直接用树链剖分处理，找出两点之间路径上最小权值就好了。
注意图有不连通的情况，所以还需要在进行树链剖分时把所有没有访问到的点都 DFS 一遍。

接下来的重头戏就是边权转点权的处理了。

显然一个边只连着一个儿子，但可能多条边连在一个父亲上，所以考虑把边权直接转到儿子的点权值上。
就像下图这样。

然后就这么交上去 WA 成狗

其实我们可以在查询时很轻松地 hack 掉原来的查询方法。
如下图。

如果我们要查询点 $4\to 5$ 路径上的最小权值，我们的输出会是 233，而实际上最小权值应是 256.
显然在 $4\to 5$ 路径上是没有 $1\to 2$ 这条边的，但经过了 $2$ 这个点，导致 $1\to 2$ 的边权值被计算在内。

如何处理这种情况呢？
只需要在最后，两点 u,v 在同一条重链上时，查询 pos[u] + 1 和 pos[v] 区间的最小值就可以了。
这个方法适用于所有边权转点权的题。

完整代码

#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;
}