fork download 
  1. /**
  2.  *    author:  orzvanh14 (  )
  3.  *    created: 23.12.2022 10:08:02
  4.  *    too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define fi first
  16. #define se second
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define eb emplace_back
  20. #define pb push_back
  21. #define TASK " "
  22.  
  23. #define ms(a, x) memset(a, x, sizeof(a))
  24. #define all(a) a.begin(), a.end()
  25. #define All(a, n) a + 1, a + 1 + n
  26.  
  27. #define LOG 20
  28.  
  29.  
  30. const int INF = 1e18;
  31. const int mod = 1e9+7;
  32. const int N = 4e5  + 5;
  33. int MOD = 998244353;
  34. int bit[200000];
  35. struct node{
  36. 	int kc, u, hk;
  37. 	bool operator<(const node& other) const {
  38.         return kc > other.kc;
  39.     }
  40. };
  41. struct edge{
  42. 	int u, v, w;
  43. 	bool operator<(const edge& other) const {
  44.         return w < other.w;
  45.     }
  46. };
  47. int n, q, m;
  48. vector<pi> adj[N];
  49. vector<pi> e[N];
  50. int par[N][LOG + 1];
  51. int p[N], sz[N];
  52. int high[N], d[N];
  53. int w[N][LOG + 1];
  54. int kq = 0;
  55. vector<edge> edges;
  56. void nhap(){
  57.     cin >> n >> m;
  58.     for(int i = 1; i <= m; i++){
  59.         int u, v, w;
  60.         cin >> u >> v >> w;
  61.         adj[u].eb(v, w);
  62.         adj[v].eb(u, w);
  63.         edges.pb({u, v, w});
  64.     }
  65. }
  66. void dfs(int u, int p, int wt){
  67.     par[u][0] = p;
  68.     w[u][0] = wt;
  69.     for(int i = 1; i <= LOG; i++){
  70.         par[u][i] = par[par[u][i - 1]][i - 1];
  71.         w[u][i] = max(w[u][i - 1], w[par[u][i - 1]][i - 1]);
  72.     }
  73.     for(auto [v, wt] : e[u]){
  74.         if(v != p){
  75.             high[v] = high[u] + 1;
  76.             dfs(v, u, wt);
  77.         }
  78.     }
  79. }
  80. int lca(int u, int v){
  81.     if(high[u] < high[v]) return lca(v, u);
  82.     int res = 0;
  83.     for(int i = LOG; i >= 0; i--){
  84.         if(high[par[u][i]] >= high[v]){
  85.             res = max(res, w[u][i]);
  86.             u = par[u][i];
  87.             // Cân bằng độ sâu
  88.         }
  89.     }
  90.     if(v == u) return res;
  91.     for(int i = LOG; i >= 0; i--){
  92.         if(par[u][i] != par[v][i]){
  93.             res = max({res, w[u][i], w[v][i] });
  94.             u = par[u][i];
  95.             v = par[v][i];
  96.             // cùng nhảy lên để tìm lca
  97.         }
  98.     }
  99.     return max({res, w[u][0], w[v][0] });
  100. }
  101. void make_set(int s){
  102.     p[s] = s;
  103.     sz[s] = 1;
  104. }
  105. int get(int a){
  106.     if(a == p[a]) return a;
  107.     return p[a] = get(p[a]);
  108. }
  109. bool union_sets(int a, int b){
  110.     a = get(a);
  111.     b = get(b);
  112.     if(a != b){
  113.         if(sz[a] < sz[b]) swap(a, b);
  114.         p[b] = a;
  115.         sz[a] += sz[b];
  116.         return true;
  117.     }
  118.     return false;
  119. }
  120. void kruskal(){
  121.     sort(edges.begin(), edges.end());
  122.     for(int i = 0; i < m; i++){
  123.         int x = edges[i].u, y = edges[i].v, w = edges[i].w;
  124.         if(union_sets(x, y)){
  125.             kq += w;
  126.             e[x].eb(y, w);
  127.             e[y].eb(x, w);
  128.         }
  129.     }
  130. }
  131. void solve(){
  132.     for(int i = 1; i <= n; i++) make_set(i);
  133.     kruskal();
  134.     high[0] = -1;
  135.     dfs(1, 0, 0);
  136.     cin >> q;
  137.     while(q--){
  138.         int a, b; cin >> a >> b;
  139.         cout << kq - lca(a, b) << nn;
  140. //        cout << lca(a, b) << nn;
  141.     }
  142. }
  143. signed main() {
  144. 	// freopen("piggyback.in", "r", stdin);
  145. 	// freopen("piggyback.out", "w", stdout);
  146. 	ios_base::sync_with_stdio(0);
  147. 	cin.tie(0);
  148. 	cout.tie(0);
  149. 	nhap();
  150. 	solve();
  151. 	return 0;
  152.  
  153. }
  154.  
Success #stdin #stdout 0.01s 22368KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/3MJLyx
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!