kruskal重构树

kruskal重构树，顾名思义，是在kruskal的时候顺便搞出来的一棵重构树，具体地说是一个堆。

先说说这个东西是怎么搞出来的吧：默认事先把边按边权从小到大排序，在kruskal的时候，如果当前加入的边连接的两个点\(x\)和\(y\)不在同一个连通块中，就新建一个节点作为\(x\)和\(y\)所在树的根节点的父亲，令这个节点的权值为这条边的权值，还有一般kruskal也要做的把并查集合并；在同一个连通块中就不管。

从模板题看看重构树的性质：BZOJ3732 Network

仔细观察发现重构树上两点的lca的权值就是这两点之间路径的最大边权的最小值。其实如果是按边权从大到小排序的话，lca的权值就是最小边权的最大值，我们就是用这条性质来这道做题的。

树剖lca最好了。

#include <cstdio>

#include <cctype>

#include <algorithm>

#define R register

#define I inline

#define B 1000000

using namespace std;

const int N = 300007;

char buf[B], *p1, *p2;

I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }

I int rd() {

    R int f = 0;

    R char c = gc();

    while (c < 48 || c > 57)

        c = gc();

    while (c > 47 && c < 58)

        f = f * 10 + (c ^ 48), c = gc();

    return f;

}

int f[N], val[N], fa[N], son[N][2], dep[N], top[N], cnt;

struct edge{int x, y, z;}e[N];

I int operator < (edge a, edge b) { return a.z < b.z; }

I int find(int x) {

    R int r = x, y;

    while (f[r] ^ r)

        r = f[r];

    while (x ^ r)

        y = f[x], f[x] = r, x = y;

    return r;

}

void dfs1(int x, int f) {

    fa[x] = f, dep[x] = dep[f] + 1;

    if (son[x][0])

        dfs1(son[x][0], x), dfs1(son[x][1], x);

}

void dfs2(int x, int t) {

    top[x] = t;

    if (son[x][0])

        dfs2(son[x][0], t), dfs2(son[x][1], son[x][1]);

}

I int lca(int x, int y) {

    while (top[x] ^ top[y])

        dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];

    return dep[x] < dep[y] ? x : y;

}

int main() {

    R int n = rd(), m = rd(), k = rd(), i, x, y;

    for (i = 1; i <= m; ++i)

        e[i] = (edge){rd(), rd(), rd()};

    for (i = 1; i <= n; ++i)

        f[i] = i;

    sort(e + 1, e + m + 1), cnt = n;

    for (i = 1; i <= m; ++i) {

        x = find(e[i].x), y = find(e[i].y);

        if (x ^ y) {

            ++cnt, f[cnt] = f[x] = f[y] = cnt, val[cnt] = e[i].z;

            son[cnt][0] = x, son[cnt][1] = y;

        }

    }

    dfs1(cnt, 0), dfs2(cnt, cnt);

    for (i = 1; i <= k; ++i)

        x = rd(), y =rd(), printf("%d\n", val[lca(x, y)]);

    return 0;

}