[TIOJ]1163. 6.施工中的道路

題目連結：http://tioj.ck.tp.edu.tw/problems/1163

最小生成樹＋利用LCA找路徑最大值。
原本我以為我寫LCA一定會寫出很多BUG然後在那邊狂刷，結果沒想到只WA一兩次而已。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
#define maxn 30004
using namespace std;
typedef pair<int,int> Pair;
struct Edge{
    int from,to,w;
    bool operator<(const Edge& x)const{
        return w<x.w;
    }
}E[50005];
struct DJS{
    int p[maxn];
    void init(){
        for(int i = 0 ;i < maxn ; i++)p[i] = i;
    }
    int query(int x){
        return p[x] == x? x : p[x] = query(p[x]);
    }
    void unite(int x,int y){
        x = p[x];y = p[y];
        p[y] = x;
    }
    bool same(int x,int y){
        return query(x) == query(y);
    }
}djs;
vector<Pair> v[maxn];
int in[maxn],out[maxn],t;
int p[maxn][16],mx[maxn][16];
bool isfa(int a,int b){return in[a] <= in[b] && out[a] >= out[b];}
void DFS(int now,int fa){
    in[now] = ++t;
    p[now][0] = fa;
    for(int i = 1; i < 16 ;i++){
        p[now][i] = p[p[now][i-1]][i-1];
        mx[now][i] = max(mx[now][i-1],mx[p[now][i-1]][i-1]);
    }
    for(Pair i : v[now]){
        if(i.F != fa)mx[i.F][0] = i.S,DFS(i.F,now);
    }
    out[now] = ++t;
}
int LCA(int a,int b){
    if(a == b)return 0;
    int maxx = 0;
    if(isfa(b,a))swap(a,b);
    else if(!isfa(a,b)){
        for(int i = 15; i >= 0 ; i--){
            if(!isfa(p[a][i],b)){
                maxx = max(maxx,mx[a][i]);
                a = p[a][i];
            }
        }
        maxx = max(maxx,mx[a][0]);
        a = p[a][0];
    }
    for(int i = 15; i >= 0 ; i--){
        if(!isfa(p[b][i],a)){
            maxx = max(maxx,mx[b][i]);
            b = p[b][i];
        }
    }
    return max(maxx,mx[b][0]);
}
int main(){jizz
    djs.init();
    out[0] = 1e9;
    int n,m;cin >> n >> m;
    for(int i = 0 ; i < m ; i++)
        cin >> E[i].from >> E[i].to >> E[i].w;
    sort(E,E+m);
    for(int i = 0 ; i < m ; i++){
        if(!djs.same(E[i].from,E[i].to)){
            djs.unite(E[i].from,E[i].to);
            v[E[i].from].PB({E[i].to,E[i].w});
            v[E[i].to].PB({E[i].from,E[i].w});
        }
    }
    for(int i = 1 ; i <= n ; i++)if(!in[i])DFS(i,0);
    int q;cin >> q;
    while(q--){
        int st,ed;cin >> st >> ed;
        if(!djs.same(st,ed))cout << "-1" << endl;
        else cout << LCA(st,ed) << endl;
    }
    return 0;
}