Advertisement
YEZAELP

E. Minimum spanning tree for each edge

Dec 4th, 2021
757
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli maxN = 2e5;
  6. const lli maxM = 2e5;
  7. const lli logN = log2(maxN);
  8. using pll = pair <lli, lli>;
  9. struct Graph{
  10.     lli i, w, u, v;
  11. };
  12. Graph graph[maxM + 10];
  13. bool is_mst[maxM + 10];
  14. lli n, m;
  15.  
  16. /// sort
  17. bool compare_w(Graph a, Graph b){
  18.     if(a.w == b.w) return a.i < b.i;
  19.     return a.w < b.w;
  20. }
  21. bool compare_i(Graph a, Graph b){
  22.     return a.i < b.i;
  23. }
  24.  
  25. /// MST
  26. lli mst_par[maxN + 10];
  27. vector <pll> mst_graph[maxN + 10];
  28. lli root(lli u){
  29.     if(mst_par[u] == u) return u;
  30.     return mst_par[u] = root(mst_par[u]);
  31. }
  32.  
  33. void mrg(lli u, lli v){
  34.     u = root(u);
  35.     v = root(v);
  36.     mst_par[v] = u;
  37. }
  38.  
  39. /// LCA
  40. lli lca_par[maxN + 10][logN + 10], lca_max[maxN + 10][logN + 10];
  41. lli level[maxN + 10];
  42. void dfs(lli u, lli p, lli lvl, lli pw){
  43.     level[u] = lvl;
  44.     lca_par[u][0] = p;
  45.     lca_max[u][0] = pw;
  46.     for(auto g: mst_graph[u]){
  47.         lli v = g.first;
  48.         lli w = g.second;
  49.         if(v == p) continue;
  50.         dfs(v, u, lvl + 1, w);
  51.     }
  52. }
  53.  
  54. /// max edge to ancestor
  55. lli MaxEdge(lli u, lli v, lli mx = 0){ /// u -> v
  56.     if(level[u] < level[v]) swap(u, v);
  57.     for(lli e=logN;e>=0;e--){ /// [2 ^ logN, 2^0]
  58.         if(level[ lca_par[u][e] ] >= level[v]){
  59.             mx = max(mx, lca_max[u][e]);
  60.             u = lca_par[u][e];
  61.         }
  62.     }
  63.     if(u == v) return mx;
  64.     for(lli e=logN;e>=0;e--){ /// [2 ^ logN, 2^0]
  65.         if(lca_par[u][e] != lca_par[v][e]){
  66.             mx = max({mx, lca_max[u][e], lca_max[v][e]});
  67.             u = lca_par[u][e];
  68.             v = lca_par[v][e];
  69.         }
  70.     }
  71.     mx = max({mx, lca_max[u][0], lca_max[v][0]});
  72.     return mx;
  73. }
  74.  
  75. int main(){
  76.  
  77.     scanf("%lld %lld", &n, &m);
  78.  
  79.     for(lli i=1;i<=m;i++){
  80.         lli u, v, w;
  81.         scanf("%lld %lld %lld", &u, &v, &w);
  82.         if(u > v) swap(u, v);
  83.         graph[i] = {i, w, u, v};
  84.     }
  85.  
  86.     /// MST
  87.     for(lli i=1;i<=n;i++) mst_par[i] = i;
  88.     sort(graph + 1, graph + m + 1, compare_w);
  89.     lli mst_sum = 0;
  90.     for(lli i=1;i<=m;i++){
  91.         if(root(graph[i].u) == root(graph[i].v)) continue;
  92.         mst_sum += graph[i].w;
  93.         mrg(graph[i].u, graph[i].v);
  94.         mst_graph[ graph[i].u ].push_back({graph[i].v, graph[i].w});
  95.         mst_graph[ graph[i].v ].push_back({graph[i].u, graph[i].w});
  96.         is_mst[ graph[i].i ] = true;
  97.     }
  98.  
  99.     /// LCA
  100.     dfs(1, 0, 1, 0);
  101.     for(lli e=1;e<=logN;e++){
  102.         for(lli u=1;u<=n;u++){
  103.             lca_par[u][e] = lca_par[ lca_par[u][e - 1] ][e - 1];
  104.             lca_max[u][e] = max(lca_max[u][e - 1], lca_max[ lca_par[u][e - 1] ][e - 1]);
  105.         }
  106.     }
  107.  
  108.     /// query
  109.     sort(graph + 1, graph + m + 1, compare_i);
  110.     for(lli i=1;i<=m;i++){
  111.         if(is_mst[i]) printf("%lld\n", mst_sum);
  112.         else{
  113.             lli w = graph[i].w;
  114.             lli u = graph[i].u;
  115.             lli v = graph[i].v;
  116.             lli mxe = MaxEdge(u, v);
  117.             printf("%lld\n", mst_sum - mxe + w);
  118.         }
  119.     }
  120.  
  121.     return 0;
  122. }
Advertisement
RAW Paste Data Copied
Advertisement