barcos.cpp

#include<bits/stdc++.h>
using namespace std;

vector<pair<int, int>> adj[100010];//adjacencias da MST
int dpmx[100100][21], dpa[100100][21];
//dpmx[i][j] guarda o maximo de pessoas que conseguem sair do i e subir 1<<j(2^i) niveis
//dpa[i][j] guarda o ancestral 1<<i de j

// struct para guardar as arestas originais
struct Edge{
    int u, v, mx;

    Edge(int a, int b, int m): u(a), v(b), mx(m){}

    bool operator < (Edge other){return this->mx>other.mx;}// sobrecarga do operador para usar o sort
};

// dsu para o algoritno de Kruskal
int pai[100100];
int tam[100100];
int nivel[100100];

int achar(int u){
    if(u==pai[u])return u;
    else return pai[u]=achar(pai[u]);
}

void juntar(int u, int v){
    u=pai[u];
    v=pai[v];

    if(tam[u]>tam[v]){
        pai[v]=u;
        tam[u]+=tam[v];
    }
    else{
        pai[u]=v;
        tam[v]+=tam[u];
    }
}

//dfs para montar a arvore com raiz em 1 e montar os casos base da LCA

void dfs(int cur){
    for(int i=0; i<adj[cur].size(); i++){
        int v=adj[cur][i].first;
        if(nivel[v]!=-1)continue;
        dpa[v][0]=cur;
        nivel[v]=nivel[cur]+1;
        dpmx[v][0]=adj[cur][i].second;
        dfs(v);
    }
}

int main(){
    ios::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, b;
    cin >> n >> b;

    vector<Edge> edges;
    //leitura das arestas
    for(int i=0; i<b; i++){
        int a, b, mx;
        cin >> a >> b >> mx;
        Edge e(a, b, mx);
        edges.push_back(e);
    }

    //descobrindo a MST usando algoritmo de kruskal

    sort(edges.begin(), edges.end());

    //coloco os valores iniciais para o dsu e o enraizamento da arvore(LCA)

    for(int i=1; i<=n; i++){
        pai[i]=i;
        tam[i]=1;
        nivel[i]=-1;
    }

    for(int i=0; i<edges.size(); i++){
            int u=edges[i].u, v=edges[i].v, mx=edges[i].mx;

            if(achar(u)==achar(v))continue;
            juntar(u, v);
            adj[u].push_back({v, mx});
            adj[v].push_back({u, mx});
    }

    //colocando os casos base da raiz e fazendo o dfs

    nivel[1]=0;
    dpa[1][0]=1;
    dpmx[1][0]=-1;
    dfs(1);

    //dpa e igual ao ancestral do binary lifting, o ancestral 1<<i de j
    /*
    o maximo de pessoas que conseguem ir de j para 1<<i
    e igual ao minimo entre o maximo de pessoas que conseguem
    ir de j para 1<<(i-1) e o maximo de pessoas que conseguem
    ir do ancestral 1<<(i-1) (dpa[j][i-1]) para o ancestral 1<<i,
    que e o ancestral i<<(i-1) do dpa[j][i-1]
    */

    for(int i=1; i<21; i++){
        for(int j=1; j<=n; j++){
            dpa[j][i]=dpa[dpa[j][i-1]][i-1];
            dpmx[j][i]=min(dpmx[j][i-1], dpmx[dpa[j][i-1]][i-1]);
        }
    }


    int c;
    cin >> c;

    /*
    para cada query crio um resp com um valor alto
    e faco ele ser o minimo entre o seu valor atual
    e o maximo de pessoas que conseguem passar pelo
    caminho que vou percorrer durante a LCA
    */

    for(int i=0; i<c; i++){
        int x, y;
        cin >> x >> y;
        int resp=1e8;

        if(nivel[x]<nivel[y])swap(x, y);

        for(int i=20; i>=0; i--){
            if(nivel[x]-(1<<i)>=nivel[y]){
                resp=min(resp, dpmx[x][i]);
                x=dpa[x][i];
            }
        }

        if(x==y){
            cout << resp << endl;
            continue;
        }

        for(int i=20; i>=0; i--){
            if(dpa[x][i]!=-1 && dpa[x][i]!=dpa[y][i]){
                resp=min({resp, dpmx[x][i], dpmx[y][i]});
                x=dpa[x][i];
                y=dpa[y][i];
            }
        }

        resp=min({resp, dpmx[x][0], dpmx[y][0]});

        cout << resp << endl;
    }

    return 0;
}