Advertisement
mickypinata

FORCE-T0609E: Minimum Spanning Tree for Each Edge

Nov 10th, 2021
640
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5. typedef pair<int, int> pii;
  6. typedef tuple<int, int, int, int> tpp;
  7.  
  8. const int N = 2e5;
  9. const int logN = log2(N);
  10.  
  11. vector<tpp> edges;
  12. vector<pii> adj[N + 1];
  13. lli ans[N + 1];
  14. int ds[N + 1], sz[N + 1], rnk[N + 1], par[N + 1][logN + 1], mxe[N + 1][logN + 1];
  15. bool isInMST[N + 1];
  16.  
  17. int dsFind(int u){
  18.     if(ds[u] == u){
  19.         return u;
  20.     }
  21.     return ds[u] = dsFind(ds[u]);
  22. }
  23.  
  24. void DFS(int u, int p, int depth, int pw){
  25.     rnk[u] = depth;
  26.     par[u][0] = p;
  27.     mxe[u][0] = pw;
  28.     for(pii nxt : adj[u]){
  29.         int v = nxt.first;
  30.         int w = nxt.second;
  31.         if(v == p){
  32.             continue;
  33.         }
  34.         DFS(v, u, depth + 1, w);
  35.     }
  36. }
  37.  
  38. int LCAFindMax(int u, int v){
  39.     int mx = 0;
  40.     if(rnk[u] < rnk[v]){
  41.         swap(u, v);
  42.     }
  43.     for(int e = logN; e >= 0; --e){
  44.         if(rnk[par[u][e]] >= rnk[v]){
  45.             mx = max(mx, mxe[u][e]);
  46.             u = par[u][e];
  47.         }
  48.     }
  49.     if(u == v){
  50.         return mx;
  51.     }
  52.     for(int e = logN; e >= 0; --e){
  53.         if(par[u][e] != par[v][e]){
  54.             mx = max(mx, max(mxe[u][e], mxe[v][e]));
  55.             u = par[u][e];
  56.             v = par[v][e];
  57.         }
  58.     }
  59.     mx = max(mx, max(mxe[u][0], mxe[v][0]));
  60.     return mx;
  61. }
  62.  
  63. int main(){
  64.  
  65.     int nVertex, nEdge;
  66.     scanf("%d%d", &nVertex, &nEdge);
  67.     for(int i = 1; i <= nEdge; ++i){
  68.         int u, v, w;
  69.         scanf("%d%d%d", &u, &v, &w);
  70.         edges.emplace_back(w, u, v, i);
  71.     }
  72.     sort(edges.begin(), edges.end());
  73.     for(int i = 1; i <= nVertex; ++i){
  74.         ds[i] = i;
  75.         sz[i] = 1;
  76.     }
  77.     lli MSTSum = 0;
  78.     for(tpp t : edges){
  79.         int w = get<0>(t);
  80.         int u = get<1>(t);
  81.         int v = get<2>(t);
  82.         int i = get<3>(t);
  83.         int ru = dsFind(u);
  84.         int rv = dsFind(v);
  85.         if(ru != rv){
  86.             MSTSum += w;
  87.             isInMST[i] = true;
  88.             if(sz[ru] > sz[rv]){
  89.                 swap(ru, rv);
  90.             }
  91.             ds[ru] = rv;
  92.             sz[rv] += sz[ru];
  93.             adj[u].emplace_back(v, w);
  94.             adj[v].emplace_back(u, w);
  95.         }
  96.     }
  97.     DFS(1, 0, 1, 0);
  98.     for(int e = 1; e <= logN; ++e){
  99.         for(int u = 1; u <= nVertex; ++u){
  100.             par[u][e] = par[par[u][e - 1]][e - 1];
  101.             mxe[u][e] = max(mxe[u][e - 1], mxe[par[u][e - 1]][e - 1]);
  102.         }
  103.     }
  104.  
  105.     for(tpp t : edges){
  106.         int w = get<0>(t);
  107.         int u = get<1>(t);
  108.         int v = get<2>(t);
  109.         int i = get<3>(t);
  110.         if(isInMST[i]){
  111.             ans[i] = MSTSum;
  112.             continue;
  113.         }
  114.         ans[i] = MSTSum - LCAFindMax(u, v) + w;
  115.     }
  116.     for(int i = 1; i <= nEdge; ++i){
  117.         cout << ans[i] << '\n';
  118.     }
  119.  
  120.     return 0;
  121. }
  122.  
Advertisement
RAW Paste Data Copied
Advertisement