Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pb push_back
- #define st first
- #define nd second
- #define int long long
- typedef pair<int,int> pii;
- typedef pair<int,pii> piii;
- const int N = 2e5+5 , M = 64;
- vector<piii> edges , MST;
- int n , m , tot , par[N] , vis[N] , sz[N] , h[N] , anc[N][M] , dist[N][M];
- vector<int> adj[N] , adjw[N];
- piii A[N];
- int find(int a){return par[a] == a ? a : par[a] = find(par[a]);}
- void unite(int x , int y){
- x = find(x) , y = find(y);
- if(x == y) return;
- if(sz[x] < sz[y]) swap(x,y);
- par[y]= x; sz[x] += sz[y];
- }
- void Kruskal(){
- sort(edges.begin(),edges.end());
- for(auto e : edges)
- if(find(e.nd.st) != find(e.nd.nd))
- unite(e.nd.st , e.nd.nd) , MST.pb(e);
- }
- void dfs(int u){
- vis[u] = 1;
- for(int i = 0 ; i < adj[u].size() ; i++){
- int v = adj[u][i];
- if(vis[v] == 0){
- anc[v][0] = u , dist[v][0] = adjw[u][i] , h[v] = h[u] + 1 , dfs(v) ;
- }
- }
- }
- void build(){
- for(int i = 1 ; i <= n ; i++){
- for(int j = 1 ; j < M ; j++){
- anc[i][j] = anc[anc[i][j-1]][j-1];
- dist[i][j] = max(dist[i][j-1],dist[anc[i][j-1]][j-1]);
- }
- }
- }
- int lca(int u , int v){
- int resp = 0;
- if(h[u] < h[v]) swap(u,v);
- for(int i = M-1 ; i >= 0 ; i--)
- if(h[anc[u][i]] >= h[v]) resp = max(resp,dist[u][i]) , u = anc[u][i];
- if(u == v) return resp;
- for(int i = M-1 ; i>= 0 ; i--)
- if(anc[u][i] != anc[v][i])
- resp = max(resp,dist[v][i]) , resp = max(resp,dist[u][i]) , u = anc[u][i] , v = anc[v][i];
- return max(resp,max(dist[u][0],dist[v][0]));
- }
- main(){
- cin >> n >> m;
- for(int i = 1 ; i <= n ; i++) par[i] = i , sz[i] = 1;
- for(int i = 1 ; i <= m ; i++){
- int x , y , z;
- cin >> x >> y >> z;
- A[i] = {x,{y,z}};
- edges.pb({z,{x,y}});
- }
- Kruskal();
- // cout << "aki:\n";
- //for(int i = 0 ; i < MST.size() ; i++)
- //cout << MST[i].st << " " << MST[i].nd.st << " " << MST[i].nd.nd << "\n";
- for(int i = 0 ; i < MST.size() ; i++){
- tot += MST[i].st;
- adj[MST[i].nd.st].pb(MST[i].nd.nd) , adj[MST[i].nd.nd].pb(MST[i].nd.st);
- adjw[MST[i].nd.st].pb(MST[i].st) , adjw[MST[i].nd.nd].pb(MST[i].st);
- }
- h[1] = 1 , dfs(1) , build();
- //for(int i = 1 ; i <= n ; i++){
- //for(int j = 0 ; j < 5 ; j++) cout << anc[i][j] << " ";
- //cout << "\n";
- //}
- //cout << "\n";
- //for(int i = 1 ; i <= n ; i++){
- //for(int j = 0 ; j < 5 ; j++) cout << dist[i][j] << " ";
- //cout << "\n";
- //}
- for(int i = 1 ; i <= m ; i++)
- cout << tot - lca(A[i].st,A[i].nd.st) + A[i].nd.nd << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement