Kruskal重構樹（貨車運輸）

。。。

和Kruskal生成樹一樣

本來是u，v連一條f的邊

現在變成建立一個點，點權為f，u v都像它連無邊權的邊

（實際上應該是u的根和v的根）

這樣樹有一些性質：

1.二叉樹

2.原樹與新樹兩點間路徑上邊權(點權)的最大（最小）值相等

3.子節點的邊權（大于等于）小于等于父親節點

4.原樹中兩點之間路徑上邊權的最大（最小）值等于新樹上兩點的LCA的點權

# include <iostream>
# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# define IL inline
# define ll long long
# define Fill(a, b) memset(a, b, sizeof(a));
using namespace std;

IL ll Read(){
    char c = '%'; ll x = , z = ;
    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? - : ;
    for(; c >= '0' && c <= '9'; c = getchar()) x = x *  + c - '0';
    return x * z;
}

const int MAXN = , MAXM = ;
int ft[MAXN], n, m, cnt, fa[MAXN][], w[MAXN], deep[MAXN], Fa[MAXN], num;
struct Edge{
    int to, nt;
} edge[MAXM];
struct Kruskal{
    int u, v, f;
    IL bool operator <(Kruskal b) const{
        return f > b.f;
    }
} road[MAXM];

IL int Find(int x){
    return Fa[x] == x ? x : Fa[x] = Find(Fa[x]);
}

IL void Add(int u, int v){
    edge[cnt] = (Edge){v, ft[u]}; ft[u] = cnt++;
    edge[cnt] = (Edge){u, ft[v]}; ft[v] = cnt++;
}

IL void Dfs(int u){
    for(int e = ft[u]; e != -; e = edge[e].nt){
        int v = edge[e].to;
        if(!deep[v]){
            deep[v] = deep[u] + ;
            fa[v][] = u;
            Dfs(v);
        }
    }
}

IL int LCA(int u, int v){
    if(Find(u) != Find(v)) return -;
    if(deep[u] < deep[v]) swap(u, v);
    for(int i = ; i >= ; i--)
        if(deep[fa[u][i]] >= deep[v]) u = fa[u][i];
    if(u == v) return w[u];
    for(int i = ; i >= ; i--)
        if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return w[fa[u][]];
}

int main(){
    Fill(ft, -);
    num = n = Read(); m = Read();
    for(int i = ; i <=  * n; i++)
        Fa[i] = i;
    for(int i = ; i <= m; i++)
        road[i] = (Kruskal){Read(), Read(), Read()};
    sort(road + , road + m + );
    for(int i = , tot = ; i <= m && tot < n; i++){
        int u = Find(road[i].u), v = Find(road[i].v);
        if(u != v){
            tot++;
            w[++num] = road[i].f;
            Fa[u] = Fa[v] = num;
            Add(u, num); Add(v, num);
        }
    }
    for(int i = num; i; i--)
        if(!deep[i]) deep[i] = , Dfs(i);
    for(int i = ; i <= ; i++)
        for(int j = ; j <= num; j++)
            fa[j][i] = fa[fa[j][i - ]][i - ];
    int Q = Read();
    while(Q--){
        int u = Read(), v = Read();
        printf("%d\n", LCA(u, v));
    }
    return ;
}