3MJLyx - Online C++0x Compiler & Debugging Tool

/**
 *    author:  orzvanh14 (  )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
// i wants to take ioi
//binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define nn "\n"
#define pi pair<int, int>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define TASK " "

#define ms(a, x) memset(a, x, sizeof(a))
#define all(a) a.begin(), a.end()
#define All(a, n) a + 1, a + 1 + n

#define LOG 20


const int INF = 1e18;
const int mod = 1e9+7;
const int N = 4e5  + 5;
int MOD = 998244353;
int bit[200000];
struct node{
	int kc, u, hk;
	bool operator<(const node& other) const {
        return kc > other.kc;
    }
};
struct edge{
	int u, v, w;
	bool operator<(const edge& other) const {
        return w < other.w;
    }
};
int n, q, m;
vector<pi> adj[N];
vector<pi> e[N];
int par[N][LOG + 1];
int p[N], sz[N];
int high[N], d[N];
int w[N][LOG + 1];
int kq = 0;
vector<edge> edges;
void nhap(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
        edges.pb({u, v, w});
    }
}
void dfs(int u, int p, int wt){
    par[u][0] = p;
    w[u][0] = wt;
    for(int i = 1; i <= LOG; i++){
        par[u][i] = par[par[u][i - 1]][i - 1];
        w[u][i] = max(w[u][i - 1], w[par[u][i - 1]][i - 1]);
    }
    for(auto [v, wt] : e[u]){
        if(v != p){
            high[v] = high[u] + 1;
            dfs(v, u, wt);
        }
    }
}
int lca(int u, int v){
    if(high[u] < high[v]) return lca(v, u);
    int res = 0;
    for(int i = LOG; i >= 0; i--){
        if(high[par[u][i]] >= high[v]){
            res = max(res, w[u][i]);
            u = par[u][i];
            // Cân bằng độ sâu
        }
    }
    if(v == u) return res;
    for(int i = LOG; i >= 0; i--){
        if(par[u][i] != par[v][i]){
            res = max({res, w[u][i], w[v][i] });
            u = par[u][i];
            v = par[v][i];
            // cùng nhảy lên để tìm lca
        }
    }
    return max({res, w[u][0], w[v][0] });
}
void make_set(int s){
    p[s] = s;
    sz[s] = 1;
}
int get(int a){
    if(a == p[a]) return a;
    return p[a] = get(p[a]);
}
bool union_sets(int a, int b){
    a = get(a);
    b = get(b);
    if(a != b){
        if(sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
    return false;
}
void kruskal(){
    sort(edges.begin(), edges.end());
    for(int i = 0; i < m; i++){
        int x = edges[i].u, y = edges[i].v, w = edges[i].w;
        if(union_sets(x, y)){
            kq += w;
            e[x].eb(y, w);
            e[y].eb(x, w);
        }
    }
}
void solve(){
    for(int i = 1; i <= n; i++) make_set(i);
    kruskal();
    high[0] = -1;
    dfs(1, 0, 0);
    cin >> q;
    while(q--){
        int a, b; cin >> a >> b;
        cout << kq - lca(a, b) << nn;
//        cout << lca(a, b) << nn;
    }
}
signed main() {
	// freopen("piggyback.in", "r", stdin);
	// freopen("piggyback.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	nhap();
	solve();
	return 0;

}