[萌新求助] 倍增+LCA

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define inf 2147483647
using namespace std;

const int maxn = 100000 + 10;
int n,m,q;
int father[maxn];
int head[maxn],cnt,a,b,c;
int f[maxn][20],val[maxn][20],dep[maxn];
struct data{
    int from,to,val;
} maps[maxn];
struct node{
    int next,to,val;
} tree[maxn];

void init();
void kruskal();
int lca(int,int);
void dfs(int,int);
int getFather(int);
bool cmp(data,data);
void add(int,int,int);

int main(){
    scanf("%d%d",&n,&m);
    for (int i = 0; i < m; i++)
        scanf("%d%d%d",&maps[i].from,&maps[i].to,&maps[i].val);
    init();
    kruskal();
    for (int i = 1; i <= n; i++)
        if (father[i] == i)
            dfs(i,0);
    scanf("%d",&q);
    for (int i = 0; i < q; i++){
        scanf("%d%d",&a,&b);
        if (getFather(a) == getFather(b))
            printf("%d\n",lca(a,b));
        else printf("-1\n");
    }
    return 0;
}

void init(){
    for (int i = 1; i <= n; i++) father[i] = i;
    memset(head,-1,sizeof(head));
    memset(val,-1,sizeof(val));
}

void kruskal(){
    int done = 0;
    sort(maps,maps+m,cmp);
    for (int i = 0; i < m; i++){
        int u = maps[i].from;
        int v = maps[i].to;
        if (getFather(u) == getFather(v)) continue;
        father[getFather(v)] = getFather(u);
        add(v,u,maps[i].val); add(u,v,maps[i].val);
        if (++done == n - 1) break;
    }
}

int lca(int x, int y){
    int minn = inf;
    if (dep[x] > dep[y]) swap(x,y);
    for (int i = 20; i >= 0; i--){
        if ((1<<i) > dep[y]) continue;
        if (dep[f[y][i]] >= dep[x]){
            minn = min(minn,val[y][i]);
            y = f[y][i];
          if (x == y) return minn;
        }
    }
    for (int i = 20; i >= 0; i--){
        if ((1<<i) > dep[x]) continue;
        if (f[x][i] != f[y][i]){
            minn = min(minn,min(val[x][i],val[y][i]));
            x = f[x][i];
            y = f[y][i];
        }
    }
    return min(minn,min(val[x][0],val[y][0]));
}

void dfs(int id, int p){
    dep[id] = dep[p] + 1; f[id][0] = p;
    for (int i = 1; (1<<i) <= dep[id]; i++)
            f[id][i] = f[f[id][i-1]][i-1],
            val[id][i] = min(val[f[id][i-1]][i-1],val[id][i-1]);
    for (int i = head[id]; ~i; i = tree[i].next)
        if (tree[i].to != p)
            val[tree[i].to][0] = tree[i].val,
            dfs(tree[i].to,id);
}

int getFather(int id){
    return id==father[id] ? id:getFather(father[id]);
}

bool cmp(data a,data b){
    return a.val > b.val;
}

void add(int a, int b, int c){
    tree[cnt].val = c;
    tree[cnt].to = b;
    tree[cnt].next = head[a];
    head[a] = cnt++;
}